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
1answer
24 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 ...
0
votes
1answer
30 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
1answer
10 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
2answers
67 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 ...
1
vote
0answers
21 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 ...
0
votes
0answers
31 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 ...
1
vote
1answer
35 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.
0
votes
1answer
68 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 ...
0
votes
0answers
49 views

Feedback vertex set

May $D=(d_1, d_2, d_3 ... d_n) \in \big\{0, 1, ... ,n-1\big\}^n.$ We build the graph $M_D$: $\forall i \in \big\{1, 2, ...,n\big\} $ we consider the sets $R_i$ and $S_i$: $R_i= \begin{cases} ...
0
votes
0answers
25 views

Maximum flow problem with non-zero lower bound

Given G = (V,E ) a directed graph, if $ X \subseteq V $ we note with $\delta ^{+}\left(X\right)$ = $\left \{ xy\in E \mid x \in X, y\in V - X \right \}$ and $\delta ^{-}\left(X\right)$ = $\delta ...
0
votes
0answers
62 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?
-2
votes
1answer
35 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.
0
votes
2answers
77 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 . ...
3
votes
1answer
43 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$
1
vote
1answer
352 views

The number of e-even connected components of a graph

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question: A connected component of a graph is called e-even if the ...
2
votes
2answers
55 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 ...
4
votes
2answers
88 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 ...
2
votes
2answers
39 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$, ...
0
votes
1answer
358 views

Complements of bipartite graphs

What constraint must be placed on a bipartite graph G to guarantee that G's complement will also be bipartite? Does it have to have at most 2 vertices on each side and be complete? Thanks
2
votes
0answers
73 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
0
votes
1answer
196 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 ...
0
votes
0answers
39 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
113 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 ...
1
vote
0answers
21 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 ...
2
votes
0answers
28 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 ...
4
votes
1answer
48 views

Measure of the clusters quality in a graph

Suppose we have a graph $G=(V,E)$ with $n$ non-overlapping subgraphs, the clusters $C_1, C_2, \dots, C_n$ which covers the graph $C_1 \cup \dots \cup C_n = G$. I'm looking for a good metric to ...
1
vote
0answers
26 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 ...
2
votes
1answer
35 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 ...
0
votes
2answers
61 views

Vertices of degree one and cut-edges

Please help solve following: 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 ...
1
vote
0answers
15 views

Labelling graph over an abelian group

I was reading about this equivalence of labellings on a graph where they mentioned about a group equivalence as a product of an automorphism with a labelling. I don't understand what kind of product ...
0
votes
1answer
34 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
68 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 $\{ ...
7
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 ...
0
votes
0answers
23 views

Let there be a cycle $C$ in graph $G$ with different vertices $x.y$, prove that there a cycle $D$ in the dual-graph $G*$ so that $D \cap C=\{x,y\}$

Let $C$ be a non-loop cycle in graph $G$, and let $x,y$ be different vertices in $C$. Show that in the dual graph G* there is cycle $D$ so that $D \cap C=\{x,y\}$ Any assistance will be appriciated! ...
0
votes
1answer
44 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 ...
2
votes
1answer
331 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
1
vote
1answer
92 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 ...
0
votes
1answer
32 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 is at ...
7
votes
1answer
387 views

Graph theory: for a connected graph, show that the size of the minimum vertex cover τ(G) is at most [(|E(G)| + 1)]/2

I'm having real trouble with this practice question: Show that $$\tau(G) ≤ \frac{|E(G)| + 1}{2}$$ for every connected graph G. What properties of a connected graph entail this inequality? Does ...
2
votes
0answers
52 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
1answer
73 views

Prove the number of total dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another not so cute problem I made from a cute problem. Prove the number of total dominating sets of a bipartite graph is never exactly divisible by $2$ ( of the ...
0
votes
2answers
20 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
136 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
33 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 ...
3
votes
1answer
35 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 ...
3
votes
1answer
461 views

Maximum cycle in a graph with a path of length $k$

I don't understand why this stands: Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Then $G$ contains a cycle ...
2
votes
1answer
227 views

Proving Cographic matroid is indeed a matroid

Given a connected graph $G=(V,E)$ let us define $M(G)=(E,I)$ where $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$. When proving $M(G)$ is a Matroid we must show: if $A,B\in I$ ...
2
votes
2answers
29 views

Non probabilistic algorithm for min-cut problem?

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?
1
vote
2answers
294 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 ...
1
vote
0answers
33 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 ...