# Tag Info

## New answers tagged graph-theory

0

Another definition of laplacian matrix M( or L) = $QQ^t$ where Q is incidence matrix. By cauchy-binet theorem, one can calculate the determinant of a rectangular matrix by considering $Q and Q^t$. So, if we take a cofactor, then it can contain twigs of a tree and since determinant of matrix containing (#nodes-1) and twigs of a tree is +/- 1. So, multiplying ...

0

Your question can be rephrased in terms of list colourings of the graph with vertices $a_{ij}$ and edges $a_{ij}a_{i'j'}$ whenever $i=i'$ or $j=j'$. If you think about it for a bit, you'll see that this graph is $K_n \square K_n$, the Cartesian product of two complete graphs. With this in mind, you might find a paper on list colourings of Cartesian products ...

0

Note that by convexity \begin{align}\sum_{uv\in E} (\rho(u)+\rho(v))&=\sum _{v\in V}\rho(v)^2\\&\ge (2n-2)n^2+2(n+1)^2\end{align} where equality holds iff $2n-2$ vertices have $\rho(v)=n$ and the other $2$ vertices have $\rho(v)=n+1$. We transform further \begin{align}(2n-2)n^2+2(n+1)^2&=2n^3+n^2+4n+2\\&=(2n+1)(n^2+1)+2n+1\\ ... 1 In general that can't be done. Suppose L_{ij}=\{1,2,\dots,n-1\} for all i,j. How are you going to choose the values for the top row without repeating a number? If you meant |L_{ij}|=n instead of |L_{ij}|=n-1, look up "Dinitz problem". 3 This is a special case of Turan's theorem, which states that a simple graph G on v vertices that does not have K_{r+1} as a subgraph has at moste = \frac{r-1}{r} \frac{v^2}{2}$$edges. For your question, r = 2 and v = 2n and the result immediately follows. A proof of Turan's theorem therefore furnishes a proof of your claim. 1 Use the following identity for the first part where you can prove it by induction or just simply apply the formula for the sum of the first h consecutive terms of a geometric progressions with a_0=2^0 and the ratio equals 2:$$2^0+2^1+\cdots+2^{h-1}=2^h-1$$For the second part, note that if only two people are playing, there's only one match deciding ... 0 This calls for some graph theory. Begin by visiting an arbitrary vertex; add each vertex it's connected to (all the things around a face, or along edges, that include the vertex), to your itinerary. Then visit a node in your itinerary and add its neighbors, that you haven't visited, to the itinerary. When you've run out of itinerary, you've found a ... 1 I believe they're talking about the 'natural' topology of a graph as a realisation of a complex whose 0-cells are the vertices of the graph, and whose 1-cells are the edges of the graph. 0 Let A\otimes B be defined as the product of matrices where you removed the diagonal i.e.:$$A\otimes B=(A-diag(A))\times(B-diag(B))$$Let A_1=A and A_n=A\otimes A_{n-1}. The number of paths of the length n without going through a vertex more than one times is equal to the sum of elements of A_n. 2 The statement is true. Q needs not to be finite. We just need that (Q,\geq) is a well-quasi order. Notation and recalls: Let \sqsubseteq be the minor ordering on graphs. We know that \sqsubseteq is a well-quasi order by Robertson–Seymour theorem. Let \sqsubseteq_L be the minor ordering on labelled graphs. Proof of: \sqsubseteq_L is a ... 2 Consider coloring the vertices one at a time, with x colors. Beginning with the upper left vertex, you have x choices of color for that vertex. Once that color is chosen, there are x-1 choices of color for the lower left vertex (it cannot have the same color as the upper left vertex). Once those colors are chosen, there are x-2 choices of color for ... 0 In such general terms, the only algorithm is exhaustion. Walk through all possible paths of your graph and check for consistency. It is possible that there is a much better way depending on your assumptions about the graph. 2 The desired sum of all (leaf) path scores can be regrouped, using the distributive law, into an expression matching the structure of the tree: (I will write V_1 instead of MWV_1.)$$ \left[\left[\left[\left[ V_1(0) \right] V_1(1) + V_2(0) \right] V_1(2) + \left[ V_1(0) \right] V_2(1) \right] V_1(3) + \left[\left[ V_1(0) \right] ...

1

Let $G$ be a bipartite graph with bipartition $(A,B)$. The idea is to apply Menger's Theorem to a new graph $G^\prime$ obtained from $G$ by adding two vertices $u$ and $v$, and joining $u$ to all vertices in $A$, and $v$ to all vertices in $B$. Now you just need to check that a matching in $G$ corresponds to a set of internally-disjoint $(u,v)$-paths in ...

1

According to my calculations in sage, there are 11 graphs (out 156) on six vertices such that $\det(I-M)=1$ and exactly two of these eleven are trees. This shows that is is going to be very difficult to determine information about cycles from the value of $\det(I-M)$. (There is nothing special about the value '1' here, for example example there are 35 graphs ...

0

By definition, a graph with degree sequence $(5,r,s,1,1,1,1,1)$ has $8$ vertices. We also know that a tree with $n$ vertices has exactly $n-1$ edges. So any tree with this degree sequence has $7$ edges. By the Handshaking Lemma, we must have $$5+r+s+1+1+1+1+1=2 \times 7=14.$$ I.e., $r+s=4$. This is sufficient to exclude all possibilities except $(r,s) ... 0 Your proof seems valid to me. This is exactly the approach I was going to take. 2 Since the graph is not a tree, it has at least a cycle. Pick a cycle$C$with the most number of vertices. I claim, it is a Hamiltonian cycle. Indeed, assume by contradiction is not Hamiltonian. Let$v$be a vertex outside the cycle. Use the pigeonhole principle, and the given condition to show that$v$is connected to two consecutive vertices on the ... 1 You are close to prove Hamiltonicity of such graphs. Just use for example induction to show that if there exists cycle$C$of length$|C|$in graph$G$then there exists a simple cycle$C_k$of length$k$for any$k$between$|C|$and$|G|$, inclusive. 0 The biggest one and the most simple one is the absence of a necessary and sufficient condition for a graph to be Hamiltonian. There are a few sufficient conditions (as far as I know) but all of them are pretty weak - or require strong conditions. The simplicity of Eulerian paths in graphs and the complexity of Hamiltonian paths is fascinating. And if I'm ... 1 If you have a graph with disjoint pairs of vertices such that you have just two edges that connect each pair of vertices in opposite directions so that you just have a bunch of disjoint cycles with 2 vertices each, then the determinant will be zero, regardless of how many cycles you have. Similarly, if you an arbitrary graph where two vertices are ... 0 If I counted correctly, the total degree sum is 68. That means each side of the bipartition must have a degree sum of 34. And 34 is not a multiple of 3 (thus no side can have a degree sum that's a multiple of 3). Now, take the side of the bipartition that doesn't have the degree 5 vertex. What about its degree sum ? 0 Okay first of all whenever you put in a Graph Theory question you must define your terms. This discipline is notorious for its ambiguous definitions. You must define what you mean by "cheapest tree" and "edge-costs". But still I'm afraid I can only be of helo for the first question. Pick an arbitrary node in$H_1 \cup H_2$. Without loss of generality, say ... 4 Because the graph is bipartite, the sum of the degrees of the vertices on the left side is equal to the sum of the degrees of the vertices on the right side. They both are equal to half of the sum of the numbers you are given. You need to show that no subset of those numbers has a sum that is equal to half of the sum of all the numbers. Hint: modular ... 1 One method to solve this problem is to use the following. Let$c(S|T)$be the cost of a cut (i.e. the total weight of the edges going from$S$to$T$, and let$c(f)$be the value of a flow going from$s$to$t$. Theorem: Let$G$be a connected graph, and let$s,t$be vertices of$G$. Then $$\min_{(S,T) \text{ cut}} c(S|T) = \max_{f \text{ flow from s to ... 0 Draw.io is really nice and user friendly. 1 In theory, you can use the nice property that the powers A^k of the adjacency matrix tell you how many paths of length k there are from each node to each other node: the graph is acyclic as long as A^k has zeroes along the diagonal for every k \geq 1. Furthermore, the matrix exponential \exp A is a positive linear combination of the powers of A, ... 0 Yes, the matrix is correct. As a side observation, the adjacency matrix being of the form$$ \begin{pmatrix} 0 & * \\ * & 0 \end{pmatrix} $$tells us that we have a bipartite graph (or rather multigraph, since you allow multiple edges). 2 I don't think there is a file easily available that contains Appel and Haken's configurations. The RSST paper mentions that in order to verify the AH paper, they would need to create a file from scratch containing all the configurations. Anyway, if you're interested in verifying the proof of the 4-color theorem, RSST simplified the process greatly, so you'd ... 1 The existence of v isn't so bad. Presumably n\geq 3 is also assumed here. If s and t are already in different components of G, then just take v to be any vertex besides s or t. If s and t are in the same component and no such v exists, then by Menger's theorem there are two paths P_1,P_2 from s to t that share no internal ... 1 The best I can think of is by assuming the tree is rooted (if your tree is unrooted, you can assign a root arbitrarily without changing its structure), and that for each vertex v, the set Ch(v) denotes the set of children of v. If v is a leaf (a degree one node), then Ch(v) = \emptyset. I guess the assumption of having a root makes sense, since ... 0 From a programming point of view, it is natural to use a recursive function: nodes in a tree = 1 (root)+ sum of nodes in each branch. To count each branch, call it again. You won't do better unless there is a regularity to the tree. For example, if each node except the leaves hs the same number of branches and all the leaves are at the same level, you can ... 0 I'm not sure if this is quite what you're looking for, but it seems close. If you represent the tree structure with a type like a tree = Empty | Node (a, a tree list) (Where a is a type variable) , you can write a sum function like you describe recursively (in some functional pseudocode): sum Empty = 0 sum Node (_,[]) = 1 sum Node (y,x:xs) = 1 + sum ... 0 It seems to me that you want an exact expression for this probability. Here is one such formula albeit it does not have a nice closed form. Fix some vertex u in G(n,p). Let's define d(u) = \max_v d(u,v), where d(u,v) is the distance between u and v. So you are interested in P(d(u) \leq \ell) for any \ell \in [1,n-1]. Let$$A_\ell:=\{(k_1, ... 1 Assume that the vertex set of$G$is$\{1,\ldots,n\}$. If$i$and$j$are not adjacent, set$B_{i,j}=0$. If$i$and$j$are adjacent and$i<j$, set$B_{i,j}=1$and$B_{j,i}=-1$; if$i>j$set$B_{i,j}+-1$and$B_{j,i}=1$. Now$B$is skew symmetric and$\det(B)$is the square of the number of perfect matchings of$G$. 3 Theorem 1.1 of the linked paper says the following: Let$C_m$be a cycle,$m\ge3,$and$P_n$a path,$n\ge2.$Let the vertices of$C_m$be labeled$0,1,\ldots,m-1$and let the vertices of$P_n$be labeled$0,1,\ldots,n-1$. Then$C_m\times P_n$is bipartite.$C_m\times P_n$is connected if and only if$m$is odd.$C_m\times P_n$consists of two ... 0 Hint: If a walk is not a path, there is a repeated vertex: Something like this:$x,a,b,...,i,...,i,...y$. But then the segment$i...i$can be removed and replaced by a single$i$giving a shorter walk from$x$to$y$. 1 Hint: if you have not proved this already, try to show that every$u$-$v$walk in a graph contains a$u$-$v$path. Given this, consider your walk from$x$to$y$of length$k$. This walk contains a path. If the path is not equal to the entire walk, what can you say about the length of the path? How might this contradict$d(x,y)=k$? 2 Hint: consider$T=(w_1,\dots,w_m)$a path of minimal length so that$w_1$lies in$P$and$w_m$lies in$Q$. Using minimality, can you show that this path satisfies the desired property? 0 The answer is no. the Symbol$\Theta (n)$is related to Average case for set of (bigger) n. So with one tree you couldn't say the tree with one-node has$\Theta (n)$in height and width. 0 Hint: Consider each number separately. What pairs$\{1,x\}$have a prime factor in common?$1$has no prime factors, so there is no such$x$. What pairs$\{2,x\}$have a prime factor in common?$2$is the only prime factor of$2$, so only even numbers would share a prime factor with$2$. So far we have:$1 \rightarrow \emptyset2 \rightarrow ...

0

I remember doing this a while ago: "given set $A$, let $B$ be the complement of $\infty$ in $\mathbb C\setminus A$". I did not find any notation or term for this thing, But I know that the term filled-in Julia set is in wide use, and it means precisely the operation you describe, applied to the Julia set of something. So, to generalize this to an arbitrary ...

0

Q1. In the way you set your problem, this condition is needed only if you approximate your inverse by this sum. Otherwise you only need non-singularity for $(I-\alpha A)$ namely $1/\alpha$ should not equal any of eigenvalues of $A$. But I think you have deeper analyze your problem, the nature of $b,x,\alpha$. It might happen that without of the condition ...

0

As for 1), it seems you got the right idea but what does "Every two vertices include adjacent ones as well." mean ? My personal way of saying it would be : if you have two vertices $u, v$ at distance 3 or 5, then necessarily there's a vertex at distance 2 from $u$ on the shortest $u - v$ path (That's what point 2. says !). So the only available odd ...

1

I find it easier to show that there are at least two such vertices for $n \geq 2$, using induction. You can verify easily, as a base case, that every connected graph on 2 vertices has at least two vertices that don't disconnect the graph. Now take a connected graph $G$ with $n$ vertices, assuming the statement holds for every connected graph with less than ...

2

Counter argument to outline the incorrectness of the statement you numbered as (3): Imagine you have a circle, and on that circle spread equally 10 points. Outside the circle draw 10 points and connect each of the outside point to exactly one point on the circle that is not connected to any other point outside the circle. The points on the circle determine ...

0

Your proof doesn't seem correct because you could have a cycle and then have one edge going out to a distinct connected component for every vertex in the cycle. Then it's possible that you will always get a disconnected graph when you remove each of the vertices in the cycle. Or am I missing something about what $\delta(G) > 1$ means?

1

Given an arbitrary bipartite graph $G$ with parts $A,B$ such that $|A|=m \le n = |B|$, the number $M$ of matchings that cover all $m$ vertices in $A$ can be expressed by a summation of $\binom{n}{m}$ permanents: $$M = \sum_{R\in \mathcal{S}} \operatorname{perm} I_R$$ where the summation is taken over all the incidence matrices $I_R$ for subgraphs $G \cap ... 0 Not 100% sure this works, but I think it does, and it's slightly different from what fahrbach is suggesting. Do a first sweep of Dijkstra to compute the distance from the destination to every other node (in terms of vertices visited) and store that information on each node. Then run Dijkstra on the original problem, with a little tweak: when you complete ... 2 There are some details for you to fill in, but here is an outline argument that seems to work. The automorphism group of$G$is isomorphic to the set of permutation matrices$P$such that$P^{-1}AP = A$; i.e., the permutation matrices that commute with$A$. Now,$A$is similar to a diagonal matrix$D\$, with the (distinct) eigenvalues on the diagonal. The ...

Top 50 recent answers are included