# Tag Info

## New answers tagged graph-theory

0

Label all the vertices $V = \{v_1, \dots, v_n\}$. This formula is supposed to represent the average of all the shortest paths in the graph. Hence, given a node $v_1$, the average length of shortest paths emanating from $v_1$ is $$\frac{1}{n-1}\sum_{i\neq 1}d(v_1, v_i),$$ since there are $n-1$ vertices distinct from $v_1$. Likewise, the average of shortest ...

0

I know nothing about spectral clustering, but here is one use of Laplacians in directed graphs I do know. Kirchhoff's matrix tree theorem gives that the number of spanning trees on a directed (multi)graph in the determinant of the reduced Laplacian. With the appropriate definitions the the theorem also holds for directed graphs, see here. As the link shows ...

0

Not sure I understand your exact question, but there is an explicit formula for the measure theoretic entropy of a first order Markov chain (that is what your directed, weighted graph represents). You need to compute the stationary vector $p$ for your stochastic matrix $P$ (the one given by the weights on your directed graph) and then the formula for the ...

1

Yes they are. Here are 2 articles (1 and 2) about opinion formation and how you can represent that in terms of basic interaction between participants. I had once read that you can find a very simple process that produces Pareto distribution, which gives you a possible reason for why the distribution wealth in society looks like that. I'm sure google will ...

1

Yes. Yes, due to the collider at $C$. It seems like you're already familiar with $d$-separation. Your statement about Bayes's Theorem is correct. I do not understand what you mean in 3.1. Option A is incorrect, and Option B is correct. Option B comes from $$P(C \mid B) = P(C \cap A \mid B) + P(C \cap \overline{A} \mid B),$$ which is due to marginalization. ...

0

Several of your statements, including your conjectures, are untrue. It is true, that one of the extreme cases (all pairs of edges stay as they are) causes a disconnected graph. It is (in general) untrue that the other extreme case (all pairs of edges are switched) causes a disconnected graph (even if $G$ itself is connected). A counterexample is already ...

0

As everyone said, depends on definitions. Wikipedia (and other sources) distinguish multigraphs and pseudographs; both can have multiple edges but only the latter is allowed to have loops. Pseudographs are also called loop-multigraphs. I have not seen a version of pseudograph definition that would restrict the number of loops at the same vertex. The ...

1

Calculating the $Q_n$ for $n=0\ldots 11$ gives, $n!Q_n = A_n$ with $\{A_n\}_{n\in\mathbb N_0} = \{1,1,2,4,10,26,76,232,764,2620,9496,35696,\ldots\}$ at least the comments on http://www.oeis.org should give you some hints for the respective matching sequences.

1

g'(x) = 1 + 2x + (1+x)g(x) I am not giving the derivation in case this is a homework question, but it should be easy to work out. Once you get this, you can solve this integral using standard techniques. Try wolfram: http://www.wolframalpha.com/input/?i=g%27%28x%29+%3D+1+%2B+2x+%2B+%281%2Bx%29g%28x%29 Now to get $Q_n$ compare coefficients of x.

2

For undirected graphs this is called the line graph. In the link there is a short section on the line digraph.

1

According to Wikipedia, "Hassler Whitney (1932) proved that with one exceptional case the structure of a connected graph G can be recovered completely from its line graph." The reference is given as Whitney, H. (1932), "Congruent graphs and the connectivity of graphs", American Journal of Mathematics 54 (1): 150–168, doi:10.2307/2371086, JSTOR 2371086. ...

0

We can rewrite it as $-( f(n-1)) =\{k_1f(n-3)+k_1f(n-3)n+k_1f(n-3)n^2+k_1f(n-3)n^3+..+\infty\}+\{k_0f(n-2)+k_0f(n-2)n+k_0f(n-2)n^2+k_0f(n-2)n^3+..+\infty\}\tag1$ from $-f(n-1)=\frac{1}{1-n}(k_0f(n-2)+k_1f(n-3))\tag 2$.Taking summation up to infinity in n from both ends we get the terms involving $\sum_{n=0}^{\infty} f(n)$ on both sides. But some ...

0

Hint: A (directed) path of length $6$ can be encoded as a string of $7$ digits from $\{1,2,\ldots,9\}$, where each digit represents a vertex from $K_9$. For example, one possible path could be: $$1254367$$ But observe that since paths are undirected, we can reverse this path and it would still be the same thing. So the total number of paths of length $6$ ...

0

Recall that an isomorphism of a graph $G_1$ with a graph $G_2$ is a bijection between the vertex set of $G_1$ and the vertex set of $G_2$ that preserves adjacency. That is, a bijection $f: V(G_1) \rightarrow V(G_2)$ so that $xy \in E(G_1)$ if and only if $f(x)f(y) \in V(G_2)$. (My convention is that the edge between vertices $v$ and $w$ is denoted by ...

2

Consider the $9$ vertex. The minimum sum it can be a part of is $1 + 2 + 9 = 12$. Hence the sum of the vertices around $9$ (and including it) is always at least $12$.

1

Not completely an answer, but maybe it is useful. The program fullgen, distributed in CaGe, contains some routines that do this. The routines exactly determine the automorphism group and are written specific for fullerenes (for which you only have 28 possible groups). They are written specific for the way fullgen constructs the fullerenes, but maybe there ...

0

I see a finite structure in Tree and node coloring.. What is your take if we go with graph theory method to get an expression for general case n and later add all as series up to infinity?If we can find a sequence some thing like GP. We may end up in a finite expression

0

Let we set $a_n=f(n)$, and $$g(x) = \sum_{n=0}^{+\infty} a_n x^n.$$ Since: $$x\cdot g'(x) = \sum_{n=1}^{+\infty} n\, a_n x^{n},$$ $$x\cdot g(x) = \sum_{n=1}^{+\infty} a_{n-1} x^{n},$$ $$x^2\cdot g(x) = \sum_{n=2}^{+\infty} a_{n-2} x^{n},$$ the recursion gives that $g(z)$ is a solution of the differential equation: $$x\cdot g'(x)-5x = k_0(x\cdot ... 0 I disagree with some of the results in the N=3 column in the table above. I agree with the values cited for up through ply 5. But from that point on: ply: table value: my value: 6 1520 1680 7 1140 1260 8 390 630 9 78 126 ... 1 You probably want to use Johnson's algorithm. This finds all the cycles in a directed graph in O((n+e)(c+1)) time, where n is the number of vertices, e is the number of edges, and c is the number of cycles. Of course you can use this algorithm to find cycles in undirected graphs by creating a directed version of your undirected graph G with edges ... 0 Some keywords and starting references: Spectral clustering Community detection 0 This isn't an answer, but the following reformulation may lead to some inspiration. For given a,b\in\mathbb{N} let c=a+b. Then adjacency between a and b may be written as ab\equiv 1 mod c. But b\equiv -a mod c, so we also have a^2=b^2=-1 mod c. This suggests we should consider for what moduli we can solve x^2=-1 i.e. for which -1 is ... 1 Since each Hamiltonian takes away two edges per vertex, an obvious upper bound for the even case is \frac n2-1. For the lower bound, use the following construction: If n=2m+2, let the vertices be 0,1,2,\ldots,n-2,n-1. For d=1,2,\ldots m, we have a Hamiltonian cycle of all points except n-1 by making steps of length d (i.e. there is an edge ... 2 If f1 is in F2 then take f2 = f1. EDIT as Casteels pointed out, this is ruled out by the wording of the question. Else, T1 - f1 has two connected components say C1 and C2. T2 must have at least one edge from C1 to C2. Take that as f2. 1 Hint: A necessary condition to partition E(K_n) into edge-disjoint Hamiltonian cycles is that n divides the number of edges. 3 This is not true, \operatorname{Aut}(X)\neq A\ast B. First, note that the tree you construct is a biregular tree, where A acts by fixing a vertex and permuting its edges (and the trees extending from these edges). The group B acts similarly, and this extends to a faithful action of A\ast B. Theorem: \operatorname{Aut}(X)\neq A\ast B To see ... 2 As stated in my comment I am unsure of the distinctions that must be made between embedding undirected graphs and directed graphs. To me it seems that to embed a directed graph you just embed the underlying undirected graph then orient the edges (possibly "splitting" an edge in the the case our directed graph has an edge in both directions between two ... 3 Let n be the number of vertices of G. Then G^* also has n vertices which means G has n faces. Using V-E+F=2, we get$$E=2n-2 \,.$$If n=2 then V=E=2 which is not possible. Otherwise, the graph is planar and bipartite*, we have E\leq 2V-4, and hence$$2n-2 \leq 2n-4$$contradiction. *We actually only used that G doesn't have any ... 2 You can build an embedding inductively, since the complement of a graph in \mathbb{R}^3 is path-connected: Place your vertices at distinct points. Label the edges with some ordering E_1, E_2,\ldots, et cetera. Letting \mathcal{G}_0 denote the set of vertices, note that \mathbb{R}^3 \setminus \mathcal{G}_0 is path-connected. Thus we can represent ... 1 Hint: Embed in \mathbb{R}^3. Start by drawing it on the x,y plane with crossings OK, but make each crossing only at a point, in a reasonably "nice" way. There are then only finitely many such crossings, and perhaps one can move the edges up/down by a small perturbation to eliminate the crossings. (This is only a hint since I don't know if it can be ... 5 Proof by induction: For every complete graph K_{2n} with 2n vertices, there is a labeling of the edges with {-1,+1} such that every vertex has n edges labeled +1 and n-1 edges labeled -1. The claim is trivially true for the null graph since there are no vertices. For the graph K_2, label the single edge +1. Take a graph K_{2n} labeled ... 6 Not sure without more context, but my best guess is the mathematician was Paul Erdős and technique you are talking about is the Probabilistic Method. 7 Let V_1,V_2 be a bipartition of V that maximizes the number t of edges between V_1 and V_2. For a vertex v define the internal degree d_i(v) as the degree of v in its partite set and the external degree d_e(v) as the degree of v to the other partite set. Clearly d(v)=d_i(v)+d_e(v). We have d_i(v)\leq d_e(v): indeed, if ... 1 The correct way, it seems to me, would be writing it as follows:$$\sum_{\{i,j\}\in\cal E}i+j$$The index set is all the edges, and for each edge we sum its two vertices. Of course, this means that the vertices belong to some structure which includes addition. To your second question \{1,2\} is the set with two elements, 1 and 2. The set ... 0 I think the problem is that you are confused about what an "unlabelled graph" is. A graph consists of a set of vertices V and a set of edges, each of which is an unordered pair of vertices. I am never entirely sure what people mean when they use the term "unlabelled graph". As a data point, the definition at http://mathworld.wolfram.com/UnlabeledGraph.html ... 0 Such kind of graphs are called universal graphs, and Chung and Graham proved that there exists such a graph with O(n \log n) edges. 2 Remember the "first theorem of graph theory:"$$\sum_{v \in V(G)} \deg v =2|E(G)|,$$where V(G) denotes the vertex set and E(G) the edge set. If \deg v is odd for each vertex, what does the above say about the parity (even or odd) of |V(G)|? Once you've figured this out, you still need to translate this into a statement about the size of the graph, ... 0 Hint: Consider the sum of the degrees of all of the vertices. Every edge contributes to this sum twice, so the sum is even. What happens if you have an odd number of vertices, each with an odd degree? 0 Best known solutions for choosing up to 26 points in a lattice can be found at No Repeated Distances. It is a very hard combinatorial problem. 1 This should work: Let A' be all vertices with in-degree 0, and let A'' be their neighbors Add vertices in A' to A Add vertices in A'' to V \setminus A Remove A' \cup A'' from G and repeat steps 1-3 until the graph is empty Correctness: Since there are no edges between vertices with in-degree 0, property (i) holds for A'. As all ... 0 The density function is P_\theta = p_\theta as it is a discrete distribution with respect to the counting measure. Then is it fairly easy to write it out as an exponential family. 0 Forward edges point from a vertex to one of its descendants in the tree. Back edges point from a vertex to one of its ancestors in the tree. Cross edges point from one vertex to another vertex to which it is incomparable with respect to the ordering induced by the DFS tree. That is, (u,v) \in E' is a forward edge if u is an ancestor of v, and a back ... 1 EDIT: This answer assumes a path cannot contain repeated edges or vertices. The OP is interested in the case where edges and vertices can be repeated. See comments below. Here is an example of two non-isomorphic graphs G and H with isomorphic 2-step graphs G^{(2)} and H^{(2)}. 0 You can easily put the points on a line so that each distance is unique: If x_1,x_2,..,x_n are your n points, put them on a ray starting at O, in this order such that d(x_{i},O)=2^{i-1}. It follows that$$d(x_{i},x_j)=|2^{i-1}-2^{j-1}| \,.$$And it is easy to prove that 2^a-2^b=2^c-2^d implies (a=c) and (b=d). 0 This is called the Erdős and Sós conjecture on trees. See here. The conjecture was recently proved. 0 Put all the vertexes on the first \vert v\vert positive integers of the x axis (so if you have 3 vertexes, they'll be in the coordenates (1,0,0), (2,0,0) and (3,0,0). Then count the amount of edges: \vert e\vert. Now we will draw every edge in a different semiplane, so that no edges cross: Draw the first edge in the xz^+ semiplane. Let's call ... 0 The result is true for any rooted tree (assuming that the children of each node are visited in the same order regardless of the type of traversal). The key fact is that x is an ancestor of y iff x = \operatorname{lca}(x,y) (where \operatorname{lca}(x,y) denotes the lowest common ancestor of x,y). Now suppose x is an ancestor of y. Then in the ... 1 I wanted to vote up the Karolis's answer and add a comment for d=0 but I don't have enough reputation, so I write an answer. If d=0 then your graph has no edges. Any partitioning into disjoint sets A and B would render a legal bipartition, since there are no edges among the vertices in either of the sets. In particular different number of vertices ... 1 Each vertex has d edges and no two vertices in A (or B) are connected. So in total, A has |A|d edges coming out of it and B has |B|d edges going into it. Can those be different? -2 If you told me to find for a given set. c - integer of any sign. Then for the equation.$$\frac{ab-1}{a+b}=c$$using factorization. In the following manner.$$(k-n)(k+n)=4(c^2+1)$$Then the solutions are.$$a=c+\frac{k+n}{2}b=c+\frac{k-n}{2}.........a=c-\frac{k+n}{2}b=c-\frac{k-n}{2}

Top 50 recent answers are included