Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [graph-theory]

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.

0
votes
0answers
8 views

Is the complement of a directed and not strongly connected graph connected?

I'm aware this result holds for simple graphs: Given a simple graph and its complement, prove that either of them is always connected. Does it hold for directed and not strongly connected graphs?
1
vote
0answers
38 views

Unsolved problem in graph theory

During graph theory class we got a problem within graph theory that is apparently unsolved. The problem goes as follow: 'In a connected graph G, choose any three paths of maximum length. Is there ...
-1
votes
1answer
16 views

Algorithm to find a maximum weighted forest [on hold]

Given a graph G(V,E), with negative weights. - How to find a maximum weighted forest on G, and how to prove that if all weights are positive the result is a tree.
0
votes
1answer
21 views

Relationship between poor spectral expansion and poorly connected subset.

Suppose I have a $d$-regular graph $G = (V, E)$ on $n$ vertices, with second largest eigenvalue $\lambda_2 = cd$, for some $c \in (1/2, 1)$ (which means its spectral expansion is a small constant). ...
0
votes
1answer
10 views

The number of Laplacian eigenvalues of a graph in interval [3,n].

There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$). I want to know whether there exists any bound ...
-4
votes
0answers
19 views

Prove the question [on hold]

Prove that in a simple graph G, the union of two distinct paths joining two distinct vertices contains a cycle. Use induction on the sum l of the lengths of the two path for all vertex pairs. If P ...
1
vote
2answers
33 views

Relation between sizes of chains and antichains in a poset

The questions is to, Show that every partially ordered set with $n$ elements either contains a chains of size greater than $c$ or an anti-chain of size at least $n/c$. I only know definitions of ...
0
votes
0answers
31 views

Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem: We have given an edge-weighted complete graph $G$ and a finite set of natural numbers $A = \lbrace n_1,\ldots,n_k \rbrace$ (...
1
vote
1answer
35 views

Inductive Proof for Menger's Theorem

The following proof for Menger's Theorem is given in Introduction to Graph Theory as follows: Menger's Theorem. Let $u$ and $v$ be nonadjacent vertices in a graph $G$. The minimum number of ...
2
votes
0answers
40 views

Why the second smallest eigenvalue of the Laplacian of a tree is $\leq1$

I know that the second smallest eigen value of the Laplacian of a star with $n>2$ is $1$. I want to show the vice versa, i.e., if the second smallest eigen value of a tree is $1$ then the tree is ...
2
votes
1answer
18 views

Showing via Ehrenfeucht-Fraïssé games that acyclicity is not definable in FO for finite graphs

I've been working through Elements of Finite Model Theory (Leonid Libkin) and am stuck on exercise 3.4. As in the title, the question asks "Using Ehrenfeucht-Fraïssé games, show that acyclicity of ...
4
votes
1answer
43 views

Let $G = (V,E)$ be a tree, then $G$ is a caterpillar graph $\iff$ The line graph of $G$ contains a Hamiltonian path.

Here the line graph $L(G)$ of $G$ is defined by $L(G) := (E,\{ef : e,f \in E, e \bigcap f \neq \oslash\})$. I think I have an argument for the forward direction. If G is a caterpillar graph on $n$ ...
-2
votes
0answers
20 views

What are the areas in Cryptography where Graph Theory is applied? [on hold]

We are to start a project on 'The role of Graph Theory on Cryptography'. We are studying more about this and need to know the areas where GT is effectively applied in Cryptography.
0
votes
1answer
14 views

What does “maximal number of closed cutting curves that do not disconnect the graph into multiple components” mean?

What does "maximal number of closed cutting curves that do not disconnect the graph into multiple components" mean? Particularly, what does closed cutting curves mean?
5
votes
2answers
64 views

Random graphs with a hamiltonian path

Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are ...
3
votes
1answer
52 views

Are these trees useful and how are they named in the literature

I am working in a project with trees and it turns out that the specific problem I am trying to attack is easy on some types of trees. If we consider the rooted layout of the tree with the root being ...
1
vote
0answers
32 views

Probability that a random graph will remain planar after adding an edge

According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is ...
0
votes
2answers
42 views

Tree ordering and upclosure and downclosure

I am referring Diestal book on Graph Theory($5^{th}$ Edition) In section 1.5 defines the following : Writing x $ < $ y for x ∈ rT y then defines a partial ordering on V (T ), the tree-order ...
-6
votes
0answers
31 views

INTERESTING PROBLEM ON GRAPH THEORY [duplicate]

A graph $G$ has order $n=3k+3$ for some positive integer $k$. Every vertex of $G$ has degree $k+1,k+2,k+3$. Prove that $G$ has at least $k+3$ vertices of degree $k+1$ or at least $k+1$ vertices of ...
1
vote
0answers
29 views

How rich is the class of “vertex-transitive graphs”?

I wonder how rich the class of vertex-transitive graphs is. Of course, "richness" is only vaguely defined, but let me give an example for what I mean. Example. Take the graphs of maximum degree three....
1
vote
0answers
27 views

Diffusion maps & preserving the local geometry

I am reading about diffusion maps. It is stated that: the diffusion map preserves the local geometry of the graph." We know that this embedding is based on the Markov matrix. Now, I am curious to know:...
0
votes
1answer
24 views

Inequality with chromatic number and degrees of vertices

Let $(d_1,d_2, \ldots , d_n)$ be a sequence of vertices degrees in graph $G$. Prove that $\chi(G) \le \max_{i \in \{1,2,\ldots,n \}} \min \{d_i + 1, i \}$.
0
votes
0answers
22 views

Chromatic index of k-regular graph

Let $G$ be connected $k$-regular graph. Prove that $\chi'(G) = k + 1$ if $G$ has odd number of vertices or $G$ has a bridge
1
vote
0answers
32 views

2-factor in a bipartite graph

Let $G=(A \cup B,E)$ be a bipartite graph with $|A| = |B| = n$. For a set $X \subseteq A$, let $N_i(X) \subseteq B$ be the set of vertices that have at least i neighbors in $X$. I'd like to prove: If ...
0
votes
2answers
32 views

What is a spanning path in graph theory?

I was reading graph theory by Frank Harary and he mentioned that a maximal non-Hamiltonian graph will have every two vertex joined by a spanning path. Is a spanning path just another name for a ...
0
votes
1answer
51 views

Proof the Dot Conjecture

I was reading the book Fermat's Last Theorem Simon Singh and in chapter 3 he mentions the "Dot Conjecture", and gives a proof in the appendix. However, the "proof" seems to me as a just more ...
0
votes
1answer
49 views

Do rotations of a graph count as an isomorphism?

I am taking a course on Graph Theory in the upcoming semester so I started reading through Bondy and Murty. Would rotating a graph that is an isomorphism of two graphs still count as another ...
0
votes
0answers
17 views

What does it mean that a graph dual is not unique, because the dual depends on the particular embedding?

What does it mean that a graph dual is not unique, because the dual depends on the particular embedding? I don't get what graph embeddings are and how they're related to the uniqueness of the dual. ...
0
votes
0answers
25 views

What use are graph duals?

What use are graph duals? While they can be formed and perceived to be "complements", then I have some difficulties in seeing what one needs them for.
0
votes
0answers
38 views

Is there an easy way to visually identify whether two trees are isomorphic?

Is there an easy way to visually identify whether two trees are isomorphic? http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf Informally, we say that two graphs are isomorphic if one can be ...
1
vote
0answers
18 views

Simplest definition for graph genus?

I'm trying to understand the graph genus. I've read some defs, but I still find confusing, how the genus can be reliably counted. Simplest definition for graph genus? How about: Smallest number of ...
0
votes
1answer
39 views

Possible paths between two points A and B

Assume that the following figure represents a map of part of a city very well traced, where the lines are streets. A person is at point A and you want move to point B, but the condition is that you ...
1
vote
2answers
31 views

Adjacency tables, how do they work?

I'm struggling to find out how adjacency tables work. I just have no idea where they get the numbers from. Here's an example: I've kinda figured out just by looking at the graphs and numbers how they ...
2
votes
1answer
41 views

Why do you count a loop as a double in graph degree?

Why do you count a loop as a double in graph degree? Rather than just as a single? From Wikipedia: a vertex with a loop "sees" itself as an adjacent vertex from both ends of the edge thus adding ...
3
votes
1answer
54 views

Books/Reference progression for an aspiring graph theorist [on hold]

I have just finished a first course in graph theory and finished my undergraduate degree in mathematics. I have two broad questions about research/further study in graph theory. What is the natural ...
0
votes
1answer
16 views

minor relation and topological minor relations are partial orderings of on the class of finite graphs

I have a confusion with proposition 1.73 of the Diestal book on Graph Theory which states that The minor relation and the topological-minor relation are partial orderings on the class of finite ...
0
votes
0answers
36 views

Difference between terms in graph theory.

I was searching a few articles related to the power of graphs. I came to know about the term Power Graph. Is there any difference between the power of a graph and Power Graph? It is very confusing for ...
0
votes
0answers
22 views

Are there any software or libraries(in some language) which draws all the planar graphs given the number of vertices?

I am working on interrelationships between planar and Hamiltonian graphs and for the purpose I need planar graphs for inspection. Since their number grows asymptotically, I cannot approach it manually....
0
votes
2answers
28 views

representation of a weighted multigraph using adjacency matrix.

How does an adjacency matrix represent a weighted multigraph . Heard that , each element a(i,j) of the matrix either represents the degree from vertix(i) to vertex(j) or it represents the weight?
2
votes
1answer
37 views

If we remove a strip polyomino from a strip polyomino, is the result tileable by dominoes?

A strip polyomino is a polyomino through which we can draw a path $C_1, C_2, \cdots C_k$, such that all the cells in the polyomino is in the path, and no cell is repeated in the path, and $C_i$ and $...
2
votes
1answer
82 views

Use of the integrals in the graph theory

I hope to know some good references about the use of integrals to study the graph theory: For example, it seems that $$ \int^{\infty}_{-\infty} dx \exp(-x^2/2+\lambda x^3/3!) $$ whose coefficients in ...
-1
votes
1answer
21 views

find the maximal matching for a graph

I'm studying for a theory exam. And I don´t understand how maximal matchning for biparte graph works. Could someone explain how I can find maximal matchning for example for this graph or some graph ...
1
vote
0answers
20 views

Understanding Graph Theory : Torus embedded Hypercube

I'm trying to understand the graph theory in particularly hypercubes graphs and torus graph. I have this idea of a torus embedded hypercube but i don't understand it i will be grateful if anyone ...
1
vote
2answers
46 views

Is a 'root' an intrinsic property of a tree

Is root an intrinsic property of a given tree?(Given a tree, can you uniquely determine the root?) Can't any vertex of a tree be chosen as a root? Aren't all trees rooted in that case?
0
votes
0answers
20 views

Definition of zerovalent vertex in a tree

In the paper "Recurrence relations for the number of labeled structures on a finite set" by Blatter and Specker the authors speak of univalent, zerovalent and multivalent points of a tree. It seems ...
3
votes
1answer
55 views

Terminology: The group(s) of symmetries of the Cayley graph of a group.

Please forgive me if this question is ill-defined. It's late here and I want to ask the question whilst it's still fresh in my mind. Motivation: Suppose we have a group $G$ given by a presentation $$...
1
vote
1answer
15 views

If an orientation of a tree graph has no source vertices, must the in-degree of each vertex in said orientation be equal to one?

Given any polytree $T$ (any orientation of a tree graph) such that $\forall v\in V(T)(\text{indeg}(v)\neq 0)$ does this imply that $\forall v\in V(T)(\text{indeg}(v)=1)$? I'm pretty sure its true, but ...
1
vote
0answers
28 views

Is there a closed form formula exists to count the number of non-perfect matchings in a bipartite graph given vertices and egdes count?

Given a bipartite graph with v vertices each side, and initially, all vertices are disconnected i.e., 0 edges were in the graph ...
0
votes
0answers
25 views

Graph Clustering - Capacitated VRP on a MultiDiGraph

I'm working on the problem of the CVRP on a Multi Directed non-complete graph that has been extracted from OpenStreetMaps using OSMnx. In the extracted graph I have also 'flagged' several delivery ...
0
votes
0answers
15 views

Characterizations of total unimodularity

Suppose a constraint matrix $A \in \{-1,0,1\}^{m \times n}$ is totally unimodular. Then we know that every square submatrix consisting of exactly two non-zero entries per row and per column is totally ...