# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

119 views

### Show there exists a permutation $a_{i,\sigma (i)} > \frac 1{n^2}$, Hall theorem, doubly stochastic matrix

Question: Let $A = (a_{i,j} )$ be an n by n real matrix, where n > 1, $a_{i,j}$ ≥ 0 for all i, j and the sum of elements in each row of A and the sum of elements in each column of A is exactly 1. ...
36 views

### cycle in a product of directed graphs

Does anyone know how to prove that a Cartesian product of two directed graphs $G_1 \times G_2$ has a cycle (not necessarily a Hamiltonian cycle!) if and only if one of the graphs $G_1$ or $G_2$ has a ...
82 views

### Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
39 views

### Is my induction on euler's formula sufficient? [duplicate]

$n-m+l=2$, where n=#vertices, m=#edges, l=#faces. I've been asked to demonstrate an intuitive, inductive proof (whatever the hell that means). Anyway so I've shown it's true for a tree, where ...
61 views

### Bounding the number of vertices in a graph from bellow using minimum degree and girth

I'm going through a graph theory book and apparently the number of vertices should be at least $1+\delta\sum\limits_{i=0}^{r-1}(\delta-1)^i$ for $girth=2r+1$ $2\sum\limits_{i=0}^{r-1}(\delta-1)^i$ ...
79 views

### Number of spanning trees in a wheel graph without an external edge.

How many different spanning tree contains n-element graph shown above? Determine the generating function for considered sequence. I am asking for advice.
94 views

### Finding an eigenvalue of a special cubic graph

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below: I want to prove that $0$ is an eigenvalue of the adjacency matrix ...
58 views

### Perfect matching in line graph

I am given a graph $T$ with an odd number greater than or equal to 3 of vertices. Its line graph $L(T)$ has exactly one perfect matching. I need to prove that if we remove any vertex from $T$, the ...
68 views

### Can $n$ vertices be removed so the directed graph contains no cycles?

Given a directed graph and $n\in \mathbb N$ how can we verify if there exists $A \subseteq V$ so that $\left | A \right | \leq n$ and $G-A$ does not contain cycles?
77 views

### connected graph with its vertices

Let $d_1 \leq d_2 \leq \cdots \leq d_n$ be the degrees of the vertices of a graph $G$, and suppose that $d_k \geq k$ for every $k \leq n − d_n − 1$. Show that $G$ is connected. I have no idea ...
55 views

### Graphgs Theory: Tree, 2 paths of maximum length intersect at a point [closed]

Justify that in a tree, 2 paths of maximum length intersect at a point.
48 views

### Graph Theory : trees, degrees and paths.

Justify that a tree with $n$ vertices that has a vertex of degree $k\gt 2$, hasn't got a path with length bigger than $n-k + 2$
478 views

### Prim , Kruskal or Dijkstra

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . ...
1k views

### Applications (“in everyday life”) of graph theory

EDIT another idea someone gave me was to consider flows in a network that would not only depend on the node at the beginning and at the end of a vertice but also about the vertice itself, like a ...
105 views

### Asking for some reference for square of a graph Laplacian matrix. ($L^2$ or $L^{\dagger^2}$)

I am looking for some information regarding Laplacian squared of a graph. ($L^2 or L^{\dagger^2}$) I couldn't find anything special. Specially the graphs with positive weights on edges. Any related ...
69 views

### could a spanning tree graph be expressed by a lower triangular matrix?

Suppose a directed spanning tree graph $G$, there are $n$ nodes, and the root is node $1$. We express this graph by a matrix $M_{n\times n}$. If there is an directed edge from node $i$ to node $j$, ...
27 views

### Plotting weighted nodes around a center

I am trying to plot nodes around a central node dynamically by weights of similarity. I have the weight of each node to every other node. I need to display the arrangement in such a fashion that it ...
198 views

### If $F = (V,E)$ is a group of trees , $h(F) \equiv \mid V \mid \pmod 2$?

If $F = (V,E)$ is a group of trees ( or forest ) then $h(F) \equiv \mid V \mid \pmod 2$ ? $h(F)$ is the number of e-even connected components and an e-even connected component is a connected ...
43 views

### Good and thorough online and/or free Matroid Theory references?

I'm studying a course on Matroid theory. Sadly, I can't really afford buying the textbook, so I only use the lecture notes, which aren't enough for me. Are there any good and thorough online and or/...
46 views

### About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
53 views

### notation - minimum number and at least

How can I represent this formally: The Graph of Interest (GOI) of a graph G is a subgraph of G which contains the minimum number of nodes that is sufficient to get the top-k nodes. In other words, ...
186 views

### Moscow puzzle. Number lattice and number rearrangement. Quicker solution?

I have already considered chains of numbers like $4-19, 19-9, 9-22$, to solve the problem and got the answer. However just out of curiosity, can anyone think of a better/quicker solution? (answer is ...
286 views

### Problem in game theory related to traffic networks

I have learnt game theory for a short period of time and I am not familiar with multi-player non-zero sum games. Here is a problem from my book which I am stuck: In this road network below each of $n$...
230 views

The Wikipedia article about T-joins explains: Let T be a subset of the vertex set of a graph. An edge set is called a T-join if in the induced subgraph of this edge set, the collection of all the ...
441 views

### How to calculate the expected maximum tree size in a pseudoforest

I would like to calculate the expected maximum tree size in a randomly generated pseudoforest of $N$ labelled nodes where self-loops are not permitted. Empty and single-node trees are also not ...
182 views

### The subgraph obtained by removing an edge incident to a degree 1 vertex in a connected graph

Suppose that $v$ is a vertex of degree $1$ in a connected graph $G$ and that $e$ is the edge incident on $v$. Let $G′$ be the sub- graph of G obtained by removing $v$ and $e$ from $G$. Must $G′$ be ...
144 views

### graph component formula and simple graph question

i have questions about the graphs : the first one is seems to be easier : 1 _ is there any simple graph that its nodes are two times more than its edges ? demonstrate your Answer and if the answer ...
75 views

115 views

### Automorphism group of a tournament is solvable

$(a)$ Let $X$ be a tournament, i.e. $X$ is a directed complete graph. Denote $V(X)$ the vertex set of $X$. An automorphism of $X$ is a bijection $V(X) \to V(X)$ preserving orientation. Prove that the ...
72 views

### Set of Edges e shall be in MST - will greedy help?

my question is: Let $G$ be an undirected graph with weights. I want to find the set of the edges $e ∈ E(G)$, for which a minimum spanning tree $T_e$ with minimal weight exist, so $e$ is in $T_e$. My ...
110 views

### biconnected graphs - st-numbering intution

Looking at this paper, the algorithm is done in two phases. First phase: Do a DFS search, compute the spanning tree with p[v] representing parent of v, compute the lowest ancestor (closest to the ...
50 views

### In a graph $|V|=40, |E|=80$, prove there's an anti-clique of size $\geq 8$

40 kids play 80 chess games. Prove that there are at least $8$ kids that did not play with each other. In graph terms: if there are $40$ vertices and $80$ edges, prove that there is an independent ...
243 views

### Prove or disprove this upper bound on chromatic number.

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...
462 views

### Could one be a friend of all?

The social network "ILM" has a lot of members. It is well known: If you choose any 4 members of the network, then one of these 4 members is a friend of the other 3. Proof: Is then among any 4 ...
1k views

It seems to me that Russell's paradox rather is a "paradox" concerning relations. Suppose we want to construct a graph (with finite or infinite number of nodes) and want some node to be adjacent ...
83 views

### Representing Petersen graph in root system $E_6$

It is well-known that Petersen graph is an strongly regular graph with parameters (10,3,0,1) and can be considered as complement graph of $L(K_5)$ and its spectrum is $\{3,1^5,(-2)^4\}$. Also, It is ...
46 views

### a question on graph theory

This is Exercise 13 on page 189 of Reinhard Diestel of Graph Theory Given a tree $T$, find an upper bound for $ex(n,T)$ that is linear in $n$ and independent of the structure of $T$, i.e., ...
54 views

### How to know if the graph is an interval graph?

Suppose we have graph $G =(V, E)$ that $V(G) = {a, b, c, d, e}$ and $E(G) = {ab, ad, bc, be, cd, de}$ How should I know if this is an interval graph or not?
79 views

### Is there a structure similar to a graph but which includes a sense of direction, like north, west, east, south?

I understand that graphs do not have any notion of "facing", that is, a sense of relative or cardinal directions. Using a conventional graph, it's not possible to say "go left at vertex A," as far as ...
156 views

### How many ways to visit 4 cities so that each city is visited exactly 4 times without visiting the same city twice in a row?

The inclusion-exclusion principle doesn't work. Example of good path is: $$1\to 2\to 1\to 4\to 3\to 2\to 1\to 4\to 3\to 2\to 1\to 3\to 2\to 4\to 3\to 4$$ This one isn't:  1\to 2\to 1\to 1\to 3\...
47 views

### Find minimal edge set to remove such that each remaining component is spanned by one node

Suppose I have a weighted undirected graph $G$. I want to find a set of edges $E_{rem}$ to remove from $G$ and create $G'$ such that in every component of $G'$, there is at least one node connected ...
106 views

### How to eliminate some edges of a lattice to get exactly k paths?

We have an $n$ by $n$ lattice. We want to find a way to eliminate some edges, so that there are exactly $k$ paths from $(1,1)$ to $(n,n)$ of length $2n-2$. (this means our paths should be NE). I don't ...
88 views

### Convergence of monotone boolean network in the worst case

I'm looking for (upper bound) convergence of increasing monotone boolean network (network composed only with OR, AND, identity ($f_i(x)=x_j$) functions) in asynchronous updating mode. It means that if ...
Suppose that $F_q$ is a field with $q$ elements. Consider all $2\times d$ matrices with entries in $F_q$, so we have $q^{2d}$ matrices. Consider each matrix as a vertex, and two vertices $A$ and $B$ ...
### $G^k$ is k-connected - different approach for proof
Question: For a connected graph $G = (V, E)$ and a positive integer $k$, let $G^k$ be the graph with vertex set $V$ , where two vertices are connected by an edge if and only if their distance in $G$ ...