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,164
questions
0
votes
0
answers
45
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?
- 11
0
votes
0
answers
27
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^...
- 199
1
vote
0
answers
43
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 ...
- 159
5
votes
2
answers
409
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 ...
- 3,972
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 ...
- 3,972
1
vote
0
answers
68
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 ...
- 61
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, ...
- 5,045
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$,...
- 101
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_{...
- 145
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 $...
- 3,972
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 $\...
- 4,969
1
vote
0
answers
107
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:/...
- 10.1k
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
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 ...
- 12.7k
2
votes
0
answers
114
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 ...
- 2,027
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 ...
- 9
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 $\...
- 41
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 ...
- 41
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 ...
- 1,615
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
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 ...
- 45.5k
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$...
- 181
4
votes
1
answer
279
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|\...
- 41
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 ...
- 181
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 ...
- 105
0
votes
0
answers
30
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 ...
- 101
1
vote
0
answers
52
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 ...
- 111
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$ ...
- 31
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 ...
- 11
2
votes
1
answer
142
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$. ...
- 3,157
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 ...
- 1,305
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 ...
- 15.6k
6
votes
1
answer
151
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, ...
- 1,262
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 ...
- 1,262
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) \...
- 45.5k
1
vote
3
answers
167
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\}$ ...
- 45.5k
1
vote
1
answer
31
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 ...
- 1
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]^...
- 45.5k
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 ...
- 43
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 ...
- 45.5k
1
vote
2
answers
415
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 ...
- 139
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 ...
- 115
3
votes
2
answers
108
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 ...
- 31
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 ...
- 1,615
0
votes
0
answers
55
views
Names for product-like algebras involving a "duo of directed pseudoforests"
I am looking for the names (and/or for any information regarding) two algebras, one "free" and one "restricted" by an equivalence class.
In both cases, there is an (infix) binary ...
