Tag Info

Hot answers tagged

3

The phrase "maximal clique" is usually used in terms of a subgraph of a given graph $G$. So a subgraph $H$ of a graph $G$ is a maximal clique in $G$ if $H$ is isomorphic to a complete graph and there is no vertex $v \in V(G)\backslash V(H)$ so that $v$ is adjacent to each vertex of $H$. In other words, a subgraph $H$ of a graph $G$ is a maximal clique in ...


3

For your second graph I would use the axiom of Total Adjacency: Given a graph $G$ which is the join of a single vertex $u$ with another graph ($u$ is adjacent to all other vertices) then $u$ must have a colour different from all other vertices; hence $P(G,t) = t \times P(G-u,t-1)$. As previously discussed we then will have, by Complete Intersection: ...


3

Yes. This is essentially the proof that studiosus suggests: Let $X_1$ and $X_2$ be two finite generating sets of $G$, and $S_1$ and $S_2$ the associated Schrier graphs. Map the vertices of $S_1$ to the vertices of $S_2$ via the identity map (the vertices in both cases are just cosets of $H$). Note that any graph is quasi-isometric to its set of vertices ...


2

Damned if I know. Let me try and follow my nose here. The diameter of $G$ is at least $3$, what does that mean? It means there are two vertices $u,v$ in $G$ such that $\operatorname d(u,v)\ge3$. And we want to show that the complement $\bar G$ has a dominating set containing at most $2$ vertices. Hmm. Maybe I can show that $\{u,v\}$ is a dominating set for ...


2

There are exactly $|v|^2=k^2$ options for closed walks beginning with $v$ and ending with $v$ that are not $4$-cycles. So, each entry of the diagonal of $A^4$ will have an extra $k^2$ walks that are not $4$-cycles, which means that if $a_i$ is the number of $4$-cycles beginning and ending with vertex $i$, we can rewrite the $i^\text{th}$ diagonal entry as ...


2

By 2-colorable graph I think is meant a coloring of nodes, so that any edge is between nodes of different colors, i.e. a bipartite graph. Consider how to partition the $n$ nodes so that the number of edges by connecting all possible pairs will be largest. Roughly we divide the nodes into two equal groups. In the simplest case $n$ is even and we get $n/2$ ...


2

No. Any strongly regular graph on a prime number of vertices, must be a conference graph, which means that if it has $p$ vertices then its parameters are $$ p,\ \frac{p-1}2,\ \frac{p-5}4\, \frac{p-1}4. $$ This is proved in the more recent of the books titled "Algebraic Graph Theory". Andries Brouwer maintains a table of parameter sets of strongly regular ...


2

Let $G=(V,E)$ be a connected undirected graph. If $G$ has two cycles $C_1, C_2$ that share a vertex $u$, you can find a vertex $v$ where the two cycles diverge, that is, $v\in C_1\cap C_2$ and there exist $v_1\in C_1\setminus C_1, v_2 \in C_2\setminus C_1$ such that $(v,v_1),(v,v_2)\in E$. In this case you can safely remove $(v,v_1), (v,v_2)$ from $G$, ...


2

A group has no topological structure apriori, and every group can be given a topological structure as a discrete group. Groups can also be given other topological structures, and further some of these topological structures will make the group into a topological group (the relevant functions will be continuous given these topological structures). The ...


2

Your answer is absolutely right; but, the explanation could use some work. Let me give you one way that you could explain it! The key here is that if $\xi_i$, $i=1,2,\ldots,n$, is the indicator variable of the event "person $i$ starts singing", then $X=\xi_1+\xi_2+\cdots+\xi_n$, and therefore $$ ...


2

I would like to offer an alternative interpretation of why the power series above does not converge, via its relation to transience/recurrence of the random walk. After which I will give you some suggestions of how one can make sense of the equation. Recall that the Green's function of a random walk is the matrix $G(x,y)$ defined as the expected number of ...


2

TL;DR We say that function $g$ is a restriction of $f : X \to Y$ to set $X' \subseteq X$, written $$g = f\,\Big|_{X'}$$ when the domain of $g$ is $X'$ and $g(x) = f(x)$ for all $x \in X'$. Usual definition of a graph: Usually a graph is defined as a pair $G = \langle V, E \rangle$ where $E \subseteq V \times V$ is a relation on $V$ that describes edges. ...


2

Your negation of the statement is incorrect. The correct negation would be: There exists a graph $G$ so that $K(G) \neq \lambda(G)$ and the maximum degree of $G$ is at most 3. Remember that the negation of ($p \Rightarrow q$) is ($p$ and not $q$). Your second strategy is a good start. You know $K(G) < \lambda(G) \leq 3$. Therefore $K(G) \in \{0,1,2\}$. ...


1

Hint: Try strong induction by $n$. When $n=3$, since $m \geq 3$, and your graph is a subgraph of $K_3$ it follows taht $G=K_3$. $P(1),..,P(n) \Rightarrow P(n+1):$ Erase one edge. Case 1): The graph stays connected, show that then the edge you erased must be part of a cycle. Case 2): The graph disconects. Let $m_1,m_2$ be the number of edges in the two ...


1

I suspect that the interpretation given by Sandeep Silwal is correct, with $K_k$ the complete graph on $k$ vertices. There are ${n}\choose{k}$ ways of choosing $k$ vertices from $n$ vertices, and ${k}\choose{2}$ potential edges in each $K_k$, each occurring with probability $\frac{1}{2}$. Thus the expected number of copies of $K_k$ in $G(n,\frac{1}{2})$ is ...


1

In a directed graph, the Cartesian product notation is spot on. However, in an undirected graph, I don't like it. It indicates $(v_{1}, v_{2}) \neq (v_{2}, v_{1})$. Of course, notationally, we can wave our hands based on context. I prefer $E = \{ (v_{1}, v_{2}) : v_{1}, v_{2} \in V, v_{1} \neq v_{2} \}$. This also takes care of the diagonal entries, as we ...


1

As others have mentioned, the cartesian product would include both $(u,v)$ and $(v,u)$, which is not desirable for an undirected graph. The cartesian product also includes $(v,v)$, which is not desirable for simple graphs. For a simple undirected graph with vertex set $\cal V$ and edge set $\cal E$, you could instead define $\cal E$ as a subset of ...


1

Draw a hexagon and label the vertices 1,2,3,4,5,6 clockwise. To make the graph 3-regular, we have to fill in some diagonals. First connect each vertex to the opposite vertex (1 to 4, 2 to 5, 3 to 6). It's easy to check that this graph does not contain a triangle (no vertex has two neighbors which are connected to each other). Now draw another hexagon and ...


1

I like Doug West's book called Introduction to Graph Theory. It's a breadth book, covering the basics including cycles, paths, trees, matchings, covers, planarity, and coloring. There are algorithms covered like Dijkstra, Kruskal, Ford-Fulkerson, Bipartite Matching, Huffman Encodings, and the Hungarian algorithm. There is also a lot of relevant theory you ...


1

Assume that every vertex of a planar graph $G$ has degree $6$ or more. Thus by The First Theorem of Graph Theory we have $2m\geq 6n$ where $n$ and $m$ denote the order and size of $G$. Since $G$ is planar we know that $m\leq3n-6$ and we have $3n\leq m$. Thus $3n\leq 3n-6$ which implies that $0\leq -6$ which is a contradiction. Thus every planar graph has a ...


1

A further result has been added below: You may want to require that distinct edges intersect in at at most one point. Without this additional assumption, even cycles can be drawn in the way you describe. (Take your A-B-C-D graph and move A and B to the edge CD, with A closer to C.) With this extra requirement, you definitely can’t draw an even cycle. ...


1

Take two vertices $x$ and $y$. Assuming $T$ is strongly connected, there is a directed path from $x$ to $y$. As $T$ is transitive, there is an edge $x\to y$. Inversely, there is a directed path from $y$ to $x$, and therefore an edge from $y\to x$. But now there are two edges connecting $x$ and $y$.


1

The answer depends a lot on how one defines "random cubic graph" with $n$ vertices (necessarily $n$ is even), we may try the following to find Hamilton circuits: Fix a vertex $a_1$, pick one of its neighbours $a_2$ at random. Then, assuming we have $a_1a_2\ldots a_k$ with $k\ge 2$, toss a coin to decide which of the other two (i.e. $\ne a_{k-1}$) ...


1

Assume to the contrary that no more than three vertices have degree 5 or less, so all but three have degree at least six. That mean $n \geq 6(m-3)+3 = 6m-15$ or $m \leq \frac{n+15}{6}$. But you have shown that $m \geq 3n$. Combining, we get $\frac{n+15}{6} \geq 3n$ or $17n \leq 15$, which is absurd.


1

The book "Chromatic Polynomials and Chromaticity of Graphs" by F. M. Dong, Khee Meng Koh, and K. L. Teo has an entire chapter dedicated to results about chromatically equivalent graphs. See chapter 3, and particularly Theorem 3.2.1. ...


1

I came across a research paper from 1972 which addresses this question. Let $\chi(G, \lambda)$ be the chromatic polynomial. Then $(-1)^{V} \chi(G, -1)$ is the number of acyclic orientations of $G$, your graph. I let $V$ be the vertex count of $G$. This is Theorem 1.3 of the paper. http://www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf


1

There are, on average, $\binom{n-1}{x}$ ways to choose an outgoing neighborhood of $v_{1}$. The vertex $v_{2}$ will be $\binom{n-2}{x-1}$ of these neighborhoods. So simply divide out: $$P( (v_{1}, v_{2}) \in E(G) ) = \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$$ Now for a two-cycle, we want an outgoing arc from $v_{2}$ to $v_{1}$. The probability is the ...


1

Let $T$ be a spanning tree in a connected plane graph $G$. Let $G^*$ be the dual graph corresponding to an embedding of $G$ in the plane, and let $T^*$ be the subgraph of $G^*$ consisting of the edges of $G^*$ that correspond to the edges of $G$ not in $T$. We want to prove $T^*$ is a spanning tree of $G^*$. First note that $T$ has $|V(G)|-1$ edges, so ...


1

You have two cases: $m \geq n$ or $m = 1, n = 1$. Gerry Myerson covered $K_{1, 1}$ pretty well. Now if $m \geq 1$, pick a vertex $v_{1}$ from the first partition. We consider $n = 2, m = 1$ to demonstrate the concept. It is connected to the only vertex in the second partition. We then pick a different vertex in the first partition. Since no vertices in the ...


1

Have you heard of CmapTools? It's dedicated for concept maps, but if you don't mind having keywords on every arc, you could give it a try.



Only top voted, non community-wiki answers of a minimum length are eligible