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.

learn more… | top users | synonyms

2
votes
2answers
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. ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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$ ...
1
vote
1answer
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.
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
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 ...
-2
votes
1answer
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.
3
votes
1answer
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$
0
votes
2answers
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 . ...
5
votes
2answers
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 ...
0
votes
0answers
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 ...
2
votes
2answers
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$, ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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/...
2
votes
0answers
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 ...
0
votes
0answers
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, ...
5
votes
1answer
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 ...
0
votes
2answers
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$...
2
votes
1answer
230 views

Wikipedia article about T-joins

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 ...
4
votes
3answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
4
votes
2answers
75 views

Are these graphs all bipartite?

Given a number $D >0$, define a graph $G_D$ as follows. The vertices of $G_D$ correspond to points in the two-dimensional integer lattice $\mathbb{Z} \times \mathbb{Z}$. A pair of vertices $\{ p,...
1
vote
1answer
112 views

Photo Booth problem

There are $n$ people. There is a Photo Booth in which they can enter at most $m$ people at one time. They want to get a picture with all other person together. Please solve the $F(n,m)$; minimum ...
2
votes
2answers
270 views

Optimal way of visiting each metro station of Montreal

As weird as it sounds, my girlfriend asked me to come up with a way of visiting each metro stations in Montreal as fast as possible. By this she means that she wants to avoid visiting a station more ...
0
votes
2answers
363 views

The incidence matrix of a weighted graph

How to correctly build the incidence matrix of a undirected weighted graph? May you show a little example?
4
votes
2answers
506 views

What is the edge set of a multigraph?

An edge set of a graph is a set of doubletons, pairing edges. For example: has an edge set of $\{\{6,4\},\{4,5\},\{4,3\},\{5,2\},\{5,1\},\{3,2\},\{1,2\}\}$. A set, by definition, cannot have ...
0
votes
1answer
56 views

Diameter of a path

Show that the diameter of the path of $k+1$ vertices (known as $P_k$) is $k$. The following definitions are given: A path of length $k$ in a graph $\Gamma$ is a graph map $\gamma : P_k \rightarrow \...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
6
votes
4answers
1k views

Is Russell's paradox really about sets as such?

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 ...
6
votes
1answer
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 ...
1
vote
1answer
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., ...
1
vote
2answers
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?
3
votes
2answers
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 ...
4
votes
1answer
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\...
2
votes
0answers
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 ...
6
votes
1answer
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 ...
3
votes
1answer
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 ...
4
votes
2answers
73 views

Prove that a graph which is constructed with matrices is strongly regular

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$ ...
2
votes
2answers
113 views

$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$ ...