# Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

5,165
questions

5
votes

2
answers

159
views

### Independence number of configuration graph (consisting of all (2k-1)!! ways to partition {1,2,...,2k} into k pairs)

Let $k$ be a nonnegative integer. A configuration on $2k$ labeled points is simply a partition of the points into $k$ pairs, so for any set of $2k$ labeled points, there are $(2k-1)!!$ configurations.
...

0
votes

0
answers

47
views

### Reference for packing property and König property

Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?

0
votes

0
answers

32
views

### Largest root of the Adjacency matrix of two graphs (comparison)

Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial:
$$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...

1
vote

0
answers

46
views

### Necessary or sufficient conditions for the $k$-fold intersection to be empty in a covering with a "tree structure"

Consider a finite collection of $d$-dimensional balls $\mathfrak{B}=\{B_1,\ldots,B_n\}$ which cover a PL $d$-manifold $M$, i.e. $M=\bigcup_{i=1}^{n}B_i$. Suppose we want to compute the Euler ...

7
votes

3
answers

471
views

### Real-world examples of unweighted directed graphs

Social Networks, Internet Traffic, Citation Networks, Transportation Networks, and Biological Networks exemplify real-world instances of unweighted directed graphs. Within these domains, the Graph ...

0
votes

0
answers

26
views

### A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial

We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...

1
vote

0
answers

69
views

### Percolative process distribution not equivalent to coupon collector problem distribution

I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a ...

17
votes

1
answer

1k
views

### Can the Pythagorean Graph be finitely colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, ...

0
votes

0
answers

27
views

### Hamiltonian Circuit Counting and Classification Problem

the Problem Description
background
Consider an undirected complete graph $G_n$ with $n$ vertices, where if the numerical labels of each vertex are consecutive, then the edge weight between them is $1$,...

0
votes

0
answers

18
views

### Differential-vertex-deletion equation for graph functions $f(x_1,...,x_n;G)$ on $n$ vertices

I encountered a function $f$ defined over a graph $G$ in my research which does not satisfy a deletion–contraction recurrence but an equation of the form
$$\partial_k f(x_1,...,x_k,..x_n;G)=g(x_k, N_{...

1
vote

2
answers

176
views

### Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...

1
vote

0
answers

72
views

### Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...

1
vote

0
answers

108
views

### Vertex cleaving and edge contraction as graph morphisms

In some approaches to operads and properads, categories of trees and graphs are used as "indexing categories" for this structure (see, for instance, https://arxiv.org/abs/0902.1954 or https:/...

0
votes

0
answers

17
views

### P-equitable graph partition

I am now conducting a research in regards to p equitable graph partition problem. I need to use LP techniques to kernelize this problem parametrized by vertex cover. In basic definition of such ...

0
votes

0
answers

32
views

### How can I measure similarity between two graphs with identical topology but different edge weights

I have two graphs, G1 and G2, with exactly the same topology. Their only difference lies in the edge weights, which vary between 0 and 1.
How can I measure the similarity between G1 and G2 under these ...

1
vote

1
answer

47
views

### Complexity of maximum weight-sum matching for cycle graphs

I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...

2
votes

0
answers

115
views

### Alon Tarsi reaches its lower bound for complete multipartite graphs

Consider a complete multipartite graph $G$ with $k$ $(k\ge2)$ parts with equal number of vertices $n$, where $n$ is even. If $k=2$, it is a well known result that the Alon-Tarsi number (ATN)(The ...

0
votes

0
answers

31
views

### Eulerian Trail proof in Walk Through Combinatorics [migrated]

I'm struggling with the proof of Eulerian trail in walk through combinatorics.
As you now, the theorem states that "A connected graph G has a closed Eulerian trail if and only if all vertices of ...

0
votes

0
answers

26
views

### Does there exist a Graph Counting Lemma in the Cut density condition?

Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...

2
votes

0
answers

98
views

### Structural description of a particular set motivated by graph reconstruction

$\DeclareMathOperator\Coh{Coh}\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Aut{Aut}$In this post, I asked a question regarding a particular function $\psi$ whose construction is motivated by the ...

0
votes

0
answers

34
views

### Does this "linear-approximated" version of Graph Counting Lemma hold?

Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...

0
votes

0
answers

36
views

### Are there 4-connected planar non-hamilton multi-graphs?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...

0
votes

0
answers

28
views

### Set of enclosed convex polyhedra in a graph

Given a straight-line graph embedded in $\mathbb{R}^3$ with known vertex coordinates and edges and no edge intersections, is it possible to find all the enclosed convex polyhedra inside? If so, is ...

1
vote

1
answer

132
views

### Chromatic number of the insert-and-shift graph on $S_n$

Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ...

0
votes

0
answers

29
views

### Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges.
Call the set of edges corresponding to an edge $uv$...

4
votes

1
answer

281
views

### A question related to "Locally Sidorenko" type problem

Let $F$ be a bipartite graph and $\delta_F=\delta(F)$ be a constant. Let $p\geq 0$ be a given constant.
Let $W$ be a graphon with $\int W=p$ and for any $A,B\subseteq \left[0,1\right]$ with $|A|,|B|\...

2
votes

0
answers

83
views

### "separators" for nonplanar graphs embedded in the plane

Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...

0
votes

1
answer

85
views

### Homology of independence complex after removing a vertex

Let $G$ be a chordal graph, $I(G)$ be its independence complex, and $v \in V(G)$ be a simplicial vertex (that is, $v$'s neighborhood is a clique).
Is there a way to relate the homology of $I(G)$ and ...

0
votes

0
answers

34
views

### Asymptotic bound on the number of simple connected graphs of bounded degree

I have posted this question on Mathematics, but unfortunately no luck so far.
Let $\mathcal{G}$ be the family of simple connected graphs on $n$ vertices, where each graph has more than $m$ edges, and ...

1
vote

0
answers

53
views

### A generalized/set hamiltonian cycle problem on directed graphs

So this problem originally stems from the asymmetric generalized/set TSP problem, where I am interested in asking the question which or how many edges I can delete while maintaining feasability. The ...

0
votes

0
answers

17
views

### Bound the $\infty$-norm of the eigenvector of the second minimum eigenvalue of normalized Laplacian from below

I meet the above problem while reading a paper. The problem can be stated as below.
Consider an undirected graph $G$. Let $\mathbf{v}$ be a vector such that $\mathbf{D}^{1/2}\mathbf{v}$ is the ...

3
votes

1
answer

240
views

### Why do we get a connected 2-regular graph?

In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...

1
vote

0
answers

42
views

### If $G$ is a connected bipartite graph, then the edge ideal $I(G)$ is normally torsion free

I am studying the paper "On the Ideal Theory of Graphs" by Simis, Vasconcelos and Villarreal, Journal of Algebra 167, No. 2, 389-416 (1994), MR1283294, Zbl 0816.13003. I got stuck at theorem ...

2
votes

1
answer

144
views

### Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...

0
votes

2
answers

79
views

### Isometric path cover number of the 2 dimensional grid graph

I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...

5
votes

0
answers

121
views

### If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?

Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...

6
votes

1
answer

152
views

### Approximating distance on a finite graph with Hamming distance

For this question, all graphs are understood to be finite, simple, and undirected. The distance metric on a graph $G$ means the length of the shortest path between the given vertices, i.e., for $v_1, ...

3
votes

1
answer

55
views

### Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

I think it is true that if the comparability graph of a poset contains an asteroidal triple then it is at-least 3 dimensional. I want to know if the converse is true, i.e. if there exists no ...

3
votes

0
answers

104
views

### Finite approximability of graphs with finitely many automorphisms

In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...

4
votes

0
answers

219
views

### Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...

1
vote

3
answers

168
views

### Graph on $\mathbb{N}$ where almost every vertex is shy

The following question is loosely based on the friendship paradox.
Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ ...

1
vote

1
answer

32
views

### Homomorphisms relationship with Graph Degeneracy

Let $H, G$ be finite undirected graphs. We say that $H$ is $r$-degenerate if there exists an ordering of the vertices of $H$ such that the back degree of every vertex is at most $r$. This is ...

0
votes

0
answers

64
views

### What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...

5
votes

1
answer

190
views

### Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...

4
votes

1
answer

204
views

### Double cover the edges of a complete graph by smaller complete graphs

Suppose we have a complete graph $K_n$ on $n$ vertices. Are there any results on the ways to cover $K_n$ with $k$ copies of $K_m$, for $m<n$, such that each edge of $K_n$ is contained in exactly ...

3
votes

1
answer

114
views

### Chromatic number of triangle-free graph $[[n]]^2$ with edges of form $a<b, b<c$

I am reading (and enjoying!) Bela Bollobas' book "Modern Graph Theory", and one of the exercises shows how to construct triangle-free graphs with large chromatic number:
For any non-negative ...

1
vote

2
answers

416
views

### What is the proper name for this "tersest path" problem in Infinite Craft?

The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...

3
votes

1
answer

191
views

### Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...

3
votes

2
answers

109
views

### Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...

1
vote

1
answer

103
views

### A reliable reference for the statement every $k$-tree is uniquely $(k + 1)$-colorable

I see that every $k$-tree is uniquely $(k + 1)$-colorable in Uniquely_colorable_graph.
Wikipedia does not cite any references, even though I know that its proof is not difficult by using mathematical ...