# Tag Info

## Hot answers tagged graph-theory

6

Let $G$ be a graph with the stated properties. Let's label one of the vertices $0$. It has three neighbors, so let's label them $1$, $2$, and $3$ in some order. Then we will label the other two neighbors of $1$ with $11$ and $12$ in some order, and so on. So now as much of the graph as we know about looks like this. Since $G$ has ten vertices, we have ...

5

Second part is not correct. Intuition: since trees are not 2 vertex connected, you can fix one vertex and construct the tree such that vertices on the left has to pass through this vertex to reach vertices on the right. Then, construct 2 such trees and you will get counterexample for second part. Counterexample: $𝑇_1=𝑣_1−𝑣_2−𝑣_3−𝑣_4−𝑣_5−𝑣_6−𝑣_7−𝑣_8−... 4 Since you are considering a simple graph$\sum_{i=1}^n{\lambda_i}=\mathrm{tr}(A)=0$, and therefore$\lambda_1 = -\sum_{i=2}^n{\lambda_i}$. Now use this,$\mathrm{tr}(A^{2}) = 2e$and Cauchy-Schwarz inequality to get $$\lambda_1^2=\left(-\sum_{i=2}^n{\lambda_i}\right)^2\leq (n-1)\sum_{i=2}^n\lambda_i^2=(n-1)(2e-\lambda_1^2).$$ 3 I believe that what you are looking for are the algorithms "Color-Constant-Degree-Graph" and "6-Color-Rooted-Tree" in this paper. The 6 coloring algorithm uses a local algorithm to color the nodes of a graph by having nodes process their color based on their neighbors colors, synchronously. It does this in$O(log^*n)$time. In case you ... 3 Just to answer the easy question: For$n=5$,$K_5 - e$is$5$-universal. Any$5$-vertex planar graph can be triangulated, extending it to a$5$-vertex planar graph with$9$edges, which can only be$K_5 - e$. And since$K_5-e$has$5$vertices itself, every graph which contains all$5$-vertex planar graphs contains$K_5-e$. For$n>5$, there are multiple ... 3 Euler path is only possible if$0$or$2$nodes have odd degree, all other nodes need to have even degree - so that you can enter the node and exit the node on different edges (except the start and end point). Your graph has$6$nodes all of odd degree, that's why you can't find any Euler path. In general if there exists Euler paths you can get all of them ... 2 To elaborate on user3733558's comment, this is (probably) the binary "or" which is used to obtain the transitive closure of a graph. Since$A$and$I$are$0-1$matrices, one can interpret "0" as false 'there is no edge between$i$and$j$' and "1" as true 'there is an edge between$i$and$j$'. We work in the boolean semi-ring ... 2 The answer is yes. As I note in my comment, we can write $$\sum_{i}^d \exp(X \odot X)_{ii} = \exp(\det(X \odot X)).$$ Thus, the manifold of interest is the set of$X$for which$\det(X \odot X) = \log(d)$. In order to show that this level set is a manifold, it suffices to verify that the gradient of$f(X) = \det(X \odot X)$is non-zero at all points on the ... 2 No. For instance, consider the graph whose vertices are integers with$n$adjacent to$n-1$and$n+1$for each$n$. Then a sequence$s:\mathbb{Z}\to\mathbb{R}$is in the kernel of the Laplacian iff$s(n)$is the average of$s(n-1)$and$s(n+1)$for each$n$. Now given any two values for$s(0)$and$s(1)$, you can uniquely determine the values of$s(n)$... 2 HINT: Let$u$and$v$be non-adjacent vertices of$G$, and let$N(u)$and$N(v)$be the sets of vertices adjacent to$u$and to$v$, respectively. Since$\delta(G)\ge\frac{n-1}2$, we know that$|N(u)|\ge\frac{n-1}2$and$|N(v)|\ge\frac{n-1}2$. Use this to show that if$u$and$v$had no common neighbor, then$G$would have at least$n+1$vertices, contrary ... 1 No: in the dual graph construction, all the white vertices created have degree$4$, but the honeycomb lattice is$3$-regular. 1 It has a radius of 2, Peripherals are {a,b,c,d,e,f}, Centers are {u,v,w}, This graph is an Euler Graph, but not a Hamiltonian Graph 1 Automorphism group of$G$has order 48; permute the vertices$u,v,w$of the inner triangle any one of$6$ways, and then for each one of the 3 outer edges$e'=ab$,$cd$,$ef$, either swap the 2 endpoints of$e'$with each other or not [$2^3=8$ways to do this]. So the automorphism group has$6×8$elements. 1 Off the top of my head, every cactus graph is a unit-distance graph. This site has a lot of information for specific graph classes, like other classes of graphs that are related and other interesting information. Is there anything specific you wanted to know about them? 1 When you say The maximal outerplane graph will be obtained by the triangulation of the interior face you are referring to something like these (there are several other possibilities, too): These are not actually outerplanar graphs! There is no longer any face that contains all the vertices. So any statement that begins "Every [...] outerplanar graph ... 1 In any graph$G$, the path from$x$to$y$going through$s$is of length$d_x + d_y$, giving us an upper bound for$d_G(x,y)$. To prove the upper bound is the best we can hope for, consider the case when$G$is an odd path (odd vertices, even length). Let$x$and$y$be its endpoints and the starting point s be the middle point, such that$d(x,s)=d(y,s)$. ... 1 Since there is a unique empty graph of each order$n \geq 1$, I take it that "empty graph" in your question is meant to be shorthand for "the empty graph$E_n$on$n$vertices for a positive integer$n$". Since you need at least one color to color the vertices of$E_n$, the chromatic number of$E_n$is at least$1$. Since there are no ... 1 Yes, the Cayley graph of the group$Q_{12}$is isomorphic to a Cayley graph of the cyclic group$\mathbb{Z}_{12}$: $$G={\rm Cay}(Q_{12};a^{\pm1},b^{\pm1})\cong{\rm Cay}(\mathbb{Z}_{12};\pm2,\pm3).$$ The following mapping is an isomorphism of these graphs $$\left(% \begin{array}{cccccccccccc} e & a & a^2 & a^3 & a^4 & ba^5 & b &... 1 Yes. For a connected graph, the smallest non-zero singular value of M is the square root of the graph's algebraic connectivity. The higher the value, the denser the graph. I am not sure what can be said about the largest eigenvalue. That said, you might be able to find more using the fact that the squares of the singular values of the oriented incidence ... 1 A path is a walk with no repeated vertices. A trail is a walk with no repeated edges. A tour is a walk that visits every vertex returning to its starting vertex. A tour could visit some vertices more than once. If you visit them exactly once, then the tour is a Hamiltonian cycle. A cycle is a walk in which the end vertex is the same as the start vertex and ... 1 you've good ideas, but you are not exactly on the right track no. First a correction : the complete graph on n vertices, has \binom{n}{2} edges, so about n^2 edges, much more than in your calculation :$$\vert E(K_{3m-1})\vert = \frac{(3m-1)(3m-2)}{2}\neq \frac{(3m-1)(3m-2)}{2m}$$Then as you said the first step is showing that$R(mK_2,mK_2) > 3m−2$... 1 Let$X$be a regular graph of degree$d$. Then the largest eigen value is$d$. Total number of edges$e=\frac{nd}{2}$. Hence$ed=\frac{nd^2}{2}$.$d \leq n-1$trivially. Substituting in above we get:$e(n-1) \geq \frac{nd^2}{2} = \frac{n|\lambda|^2}{2}$. You can see that the inequality very loose for regular graph as we used the bound$d \leq n-1$. For ... 1 Here's my best intuition: The first sequence refers to the number of colored graphs whereas the second sequence refers to the number of colorable graphs. The first sequence accounts for the number of ways to color a graph whereas the second one doesn't. For example, there are two labeled 3-colorable graphs on 2 vertices, one where they are connected and the ... 1 As you mentioned in comments, it doesn't seem to matter whether minimal or minimum separating sets are meant; although a non-shrinkable separating set may have more than 5 vertices, that doesn't seem to play a further role. This statement "exactly two vertices in$S$must lie in the exterior face of$G$" isn't actually true, as seen in the example ... 1 An easy way to see that this cannot be true is to observe that your hypothesis does not change if you swap$G_1$and$G_3$. Thus if your conjecture were true, it would not only imply$G_1 \subseteq G_2 \subseteq G_3$, but also$G_3 \subseteq G_2 \subseteq G_1$and hence$G_1 = G_3\$.

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