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.
4,860
questions
0
votes
0
answers
12
views
Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices
Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...
4
votes
0
answers
139
views
Catalan numbers from matchings?
There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph.
My question is:
Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
- 15.2k
0
votes
0
answers
20
views
Applicability of matching to tour improvement
Question:
what are relevant publications that deal with matching as a means of constructing shorter tours from existing ones?
The reason for asking is that I couldn't find anything in that respect ...
- 11.7k
0
votes
0
answers
23
views
The number of maximal cliques of the intersection graphs
Are there some results about the upper bound of the number of maximal cliques (NMC) of some class of intersection graphs?
I want to know whether some classic classes of intersection graphs have ...
- 1,473
0
votes
0
answers
42
views
"How often" does pseudo-isomorphicity imply isomorphicity in graphs?
Motivation. The iterated degree matrix $\mathbb{D}(G)$ of a finite simple undirected graph $G$ gives $G$ a kind of "fingerprint" for $G$ that is calculable in polynomial time. When for two ...
0
votes
0
answers
65
views
Does it help for graph isomorphism to know power of the permutation matrix?
Here all matrices are square $n \times n$ with integer entries.
If you prefer, all entries are $0-1$.
Observation: the discrete logarithm for permutation matrices is
polynomial in $n$, since the ...
- 23.7k
1
vote
0
answers
53
views
Min-sum belief propagation not working on a chain model with equal unary potentials
Given is a chain factor graph as presented in the image below with the following properties:
Each node can take values 0 or 1
All unary potentials are equal (e.g. $U(a)=0$) for every node $a$
All ...
0
votes
2
answers
83
views
Dense vertex-symmetric graphs with high girth
I am looking for existing constructions of vertex-symmetric graphs on $n$ nodes that have a girth at least $g$ and are dense, i.e., have at least $n^{1 + \epsilon}$ edges, where $\epsilon>0$ may ...
4
votes
0
answers
130
views
Extension of Erdős-Gallai (s,t)-path theorem to directed graphs
The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498):
Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
- 41
0
votes
0
answers
52
views
Decompose directed graph into many cycles
Given is a directed graph $G$, possibly with self-loops or parallel edges, such that each vertex has the same in-degree as out-degree. I would like to decompose it into as many directed cycles as ...
- 143
3
votes
2
answers
134
views
Lower bound on the rank of a graph
[This has been edited in response to comments from Fedor Petrov]
Suppose that $n=dm$ with $d,m>1$. Consider an $n\times n$ matrix $M$ such that
All diagonal entries are equal to one
Each row has $...
- 51.7k
4
votes
1
answer
184
views
Chromatic index of an acyclic digraph
Let $G=(V, E)$ be an acyclic digraph (DAG) with all in- and out-degrees at most $k$. Is it true that the edges of $G$ may be always colored properly in $2k$ colors?
In the discussion of this question ...
- 93.6k
2
votes
0
answers
37
views
Hamming representation number of a graph
For positive integers $n \geq k$, the Hamming graph $H(n,k)$ is constructed on the vertex set $\{0,1\}^n$ in the following manner. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the number ...
7
votes
1
answer
258
views
Does a strong digraph always admit a vertex that lies on some path between $\Theta(n^2)$ pairs of vertices?
Let $G$ be a directed graph.
Call a vertex $v$ in $G$ central if there exists $\Theta(n^2)$ distinct pairs of vertices $(u,w)$ such that $v$ lies on some path from $u$ to $w$. We do not care whether ...
- 121
3
votes
0
answers
103
views
Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?
In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1.
Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
- 1,167
0
votes
0
answers
22
views
Complexity of a specific constrained maximum weight matching
Let $G(V,E)=K_n$ be a complete symmetric and edge-weighted graph with $n$ vertices and let $H$ be a Hamilton cycle in $G$, i.e. a connected $2$-factor.
Question:
what is the complexity of calculating ...
- 11.7k
0
votes
0
answers
20
views
Approximation algorithm for non-infinite diameter of sparse directed graph
There are some good approximation algorithms that compute the diameter of a sparse directed graph, for example, this one.
Consider a little variation of the definition of diameter: we rule out ...
1
vote
0
answers
62
views
Bounds for smallest non-trivial designs
Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
- 2,198
1
vote
0
answers
39
views
Existence of minimal Steiner tree
I am looking for a reference proving the existence of the minimal Steiner tree in the Euclidean Steiner tree problem:
Given N points in the d-dimensional Euclidean space, the goal is to connect them ...
- 486
2
votes
1
answer
117
views
Two ears polygon in a maximal planar hamiltonian graph
Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
- 25
20
votes
3
answers
862
views
Can a 3-regular non-1-planar graph be constructed?
A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.
I used nauty to generate all 3-regular graphs up to ...
- 1,167
7
votes
0
answers
124
views
Why is the crossing number of Tutte 12-cage 170?
From the Wikipedia entry on Tutte 12-cage , it is stated that the crossing number of Tutte 12-cage is 170, but the cited references do not seem to provide sufficient explanation for this.
Exoo, G. &...
- 1,167
0
votes
0
answers
166
views
Kelly's conjecture and a mistake of mine
I've been looking at Kelly's conjecture that every regular tournament on $2n+1$ vertices can be decomposed into $n$ edge-disjoint Hamiltonian cycles. I'm aware that a proof has been given for large $n$...
- 1,483
0
votes
0
answers
96
views
On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph
Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
- 61
0
votes
0
answers
38
views
Are $c$-edge-colored clique removal lemmas known when $c>2$?
The following is a rephrasing of the Induced Graph Removal Lemma by Alon, Fischer, Krivelevich, Szegedy:
For all $k>0$ and all $\epsilon > 0$, there is $\delta > 0$ such that the following ...
- 1,369
0
votes
0
answers
36
views
Is there a generalization of intersection graphs on surfaces?
Is there a generalization of intersection graphs on a surface (graphs whose nodes are indexed by connected compact regions of a surface and an edge exists between two nodes if their corresponding ...
- 193
2
votes
2
answers
150
views
Is the monitor cover problem of a graph NP-hard?
Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
- 21
16
votes
0
answers
248
views
Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?
My question is
Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must
$G$ have the following substructures?
i) a leafless spanning
tree;
ii) a spanning forest consisting ...
- 1,644
0
votes
0
answers
42
views
Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph
This is about graph theory.
Define an h-dimensional hyperedge as a set that contains h vertices.
A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
- 23
4
votes
2
answers
215
views
Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?
Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types.
Let $\phi: G_{P_1}\to G_{P_2}...
- 11.3k
9
votes
0
answers
153
views
Embedding a graph into Euclidean space
I want to find a map $v\mapsto \tilde v$ from the vertex set of a connected infinite graph $\Gamma$ to a Euclidean space that meets the following two conditions:
there is $\varepsilon>0$ such that ...
- 41.2k
1
vote
0
answers
54
views
Lower bound for the minimum of the maximum frequency of an element - with restrictions
Consider a family $\mathcal{F}$ of non-empty sets, with
$n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$.
It is known that of the $\binom{n}{2}$ ways ...
- 234
1
vote
1
answer
60
views
Improving a lower bound for the minimum of the maximum frequency of an element in a family of sets
[Originally posted at math.stackexchange without answer]
Consider a family $\mathcal{F}$ of $n=|\mathcal{F}|$ sets, $\emptyset \not\in \mathcal{F}$ and an universe $U(\mathcal{F})$ of $q=|U(\mathcal{F}...
- 234
5
votes
1
answer
89
views
Can we calculate the spectral radius of the universal cover for specific graphs?
Background
For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The ...
- 11k
3
votes
1
answer
132
views
For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
5
votes
1
answer
94
views
Maximal graphs with a property that is invariant w.r.t. vertex removal
Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$.
Let $g(n)$ be the maximum size of a graph of order $n$ having $P$...
- 28k
5
votes
1
answer
143
views
3D analog of the Petersen graph
If you arrange the edge skeletons of a convex regular pentagon and a regular pentagram in the right way and connect each vertex of the former to that of the latter lying under it, the result (the ...
- 2,414
1
vote
0
answers
43
views
A multi-layer version of Menger's theorem
Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...
- 1,644
4
votes
1
answer
97
views
Cover a graph with small size complete graphs
Given a complete graph with $n$ nodes, if we want to use $n$ complete subgraphs to cover the graph and ask what is the minimum possible size of each complete subgraph, the answer is $\Theta(\sqrt{n})$:...
- 43
3
votes
0
answers
125
views
Can a polytopal graph be "centrally symmetric" in more than one way?
Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...
- 11.3k
1
vote
0
answers
44
views
What is the complexity of deciding if the number of independent sets in a graph exceeds a given threshold?
Given an (undirected) graph G, let i(G) be the number of independent sets [1] in G. Given also a threshold th, the problem is to decide whether $i(G) > th$.
Are there known values of th for which ...
- 11
4
votes
1
answer
105
views
Independent sets in graphs with girth $\ge g$
A well known off-diagonal Ramsey result says that every $C_3$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(\sqrt{N\log N})$.
It is a conjecture of Erdos that every $C_4$-free ...
- 2,198
2
votes
1
answer
138
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
8
votes
0
answers
227
views
Goldberg-Seymour conjecture
I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to the Wikipedia entry on the Goldberg-Seymour conjecture, "In 2019, an alleged ...
- 18.8k
1
vote
0
answers
107
views
Independence number of a grid like graph
Given natural numbers $n$ and $k$, let $G_{n,k}$ denote the simple graph whose vertex set is $\{1,2,\ldots ,n\}$ and there is an edge between $i$ and $j$ when $|i-j|\leq k$. I am interested in the ...
- 1,205
2
votes
1
answer
81
views
Strongly regular graphs with certain parameters
Does there exist a sequence of strongly regular graphs with parameters $(n,d,\lambda,\mu)$ (so every pair of adjacent vertices have $\lambda$ common neighbours, and every pair of non-adjacent ones ...
- 408
1
vote
0
answers
51
views
Chromatic number of 2-graph vs hypergraph of point-line incidences
Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in ...
- 17.9k
8
votes
0
answers
122
views
Partial order on graphs induced by homomorphism counts
For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
- 1,982
9
votes
1
answer
412
views
Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?
I know the following problem is famous:
For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$.
This algorithm is ...
- 1,167
3
votes
0
answers
56
views
Research on lower bounds of sphericity of a graph
I am looking for references that address lower bounds on the "sphericity" of a graph.
For a finite point set in Euclidean $n$-space, if we connect each pair
of points by a line segment ...
