All Questions
Tagged with co.combinatorics graph-theory
2,302 questions
0
votes
0
answers
12
views
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs
2-regular directed graphs where the commutative property or relation holds at every vertex and abelian Cayley digraphs.
You are given a 2 regular (2-in 2-out) directed graph where you can check that ...
- 4,713
1
vote
0
answers
171
views
+50
A question relates to edge chromatic-polynomial
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
The edge chromatic polynomial $ech(G, k)$ gives the number of proper edge coloring of the $G$ with $k$ ...
- 91
0
votes
0
answers
24
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 516
1
vote
1
answer
177
views
Refinement of face vectors of the simplicial noncrossing hypertree complexes of McCammond
Einziger on page 65 of "Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions" presents the antipode of a noncrossing partition Hopf algebra as a graded sequence of partition ...
CommunityBot
- 1
4
votes
1
answer
229
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 91
5
votes
3
answers
285
views
The max-clique chromatic number of a graph
Let $G = (V,E)$ be a graph. Every clique, that is, complete subgraph, is
contained in a maximal clique with respect to $\subseteq$ (this is
an easy consequence of Zorn's Lemma). Let $\newcommand{\MC}{\...
- 13.4k
19
votes
4
answers
1k
views
Minimal graphs with a prescribed number of spanning trees
As it's long ago since Erdős died and MathOverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem that I ...
- 8,597
1
vote
1
answer
177
views
Spectral characterization of complete or complete bipartite graphs
The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs:
Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
CommunityBot
- 1
7
votes
1
answer
165
views
$|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number
Let $G=(V,E)$ be a finite, simple, undirected graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.
Hadwiger's celebrated conjecture states that $\chi(...
CommunityBot
- 1
1
vote
0
answers
123
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
0
votes
0
answers
34
views
separator and vertex-connectivity
A definition of "separator" is the following: Let $G$ is an $n$-vertex graph, then $S\subseteq V(G)$ is a separator if there is a partition $V=A\cup B\cup S$ such that $|A|,|B|\le 2n/3$ and ...
- 281
7
votes
1
answer
343
views
Can the corollary of the Ihara–Bass formula be extended to $ u^2 = 1 $?
Suppose there is a finite undirected graph $G(V,E)$ having $n$ vertices and $m$ edges.
The non-backtracking matrix $B$ is indexed by $2m$ directed edges and defined as
$$
B(a \to b, c \to d) = \delta_{...
- 6,367
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 12.7k
12
votes
1
answer
2k
views
Hobbled rook tour – Hamiltonian cycle on square grid
Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
CommunityBot
- 1
2
votes
1
answer
319
views
Why are graph embeddings defined the way they are?
In my recent question I asked about a proof for the fact that the dual of a dual graph embedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...
- 32.1k
2
votes
1
answer
111
views
Is there a ternary Cayley graph on 27 vertices that is a non-complete core?
Is there a non-complete ternary Cayley graph that is a core with $3^3 = 27$ vertices?
By a ternary Cayley graph, I mean a (simple, undirected) graph whose vertex set is $\mathbb{Z}_3^n := \bigoplus_{i ...
- 12.7k
5
votes
1
answer
383
views
Shortest polygonal chain with $6$ edges visiting all the vertices of a cube
I am trying to find which is the minimum total Euclidean length of all the edges of a minimum-link polygonal chain joining the $8$ vertices of a given cube, located in the Euclidean space. In detail, ...
CommunityBot
- 1
11
votes
1
answer
427
views
Graph chromatic numbers defined by interactive proof
Edit (2020-07-15): Since the discussion below is perhaps a bit long, let me condense my question to the following
Short form of the question: Let $G$ be a finite graph (undirected and without self-...
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 21
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 24.2k
4
votes
0
answers
67
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
2
votes
1
answer
147
views
What is the analogue of a Block-Cut Tree Decomposition in directed graphs?
Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
- 5,407
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
0
votes
0
answers
56
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
13
votes
3
answers
3k
views
Koebe–Andreev–Thurston theorem - where can I find a proof?
Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
- 13.6k
4
votes
1
answer
389
views
The existence of a specific kind of independent set in a connected graph satisfying the following property
Suppose $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words,...
CommunityBot
- 1
6
votes
2
answers
721
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 13.6k
0
votes
0
answers
45
views
Another version of Sidorenko's conjecture(?)
I would like to ask a question about Sidorenko's conjecture. Here is the background of my question:
Quasi-random graphs
A sequence of graphs $(G_n)$ is called quasi-random if it satisfies certain ...
- 349
0
votes
0
answers
36
views
Construct a maximum matching from a minimum vertex cover in bipartite graph?
Konig's theorem in graph theory says that for a bipartite graph $G$, the size of maximum matching in $G$ is equal to the size of minimum vertex cover of $G$.
Typically, one of the proofs is to ...
- 281
7
votes
0
answers
325
views
Groups of non-orientable genus 1 and 2
The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
- 185
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
1
vote
1
answer
90
views
Characterizing the family of maximal cliques of a cograph
Preamble #1
There are two common equivalent definitions of cographs:
the smallest class that includes $K_1$ and is closed under disjoint union and complementation (or join);
the finite $P_4$-free ...
- 32.1k
2
votes
0
answers
172
views
How many maximal length snakes are there?
This problem was motivated by the classic phone game Snake.
Consider the square grid graph with vertex set $V := \{1, \dots, N\}^2$, for fixed odd positive integer $N$, and an edge between $(x, y)$ ...
- 6,155
4
votes
0
answers
90
views
Definition of Loop in an Oriented Matroid
I had posted this on Stackexchange because I don't believe this is a particlarly difficult question, but there were no answers, so I'm posting it on here now.
I just had a quick question about the ...
- 61
2
votes
2
answers
210
views
Rank of adjacency matrix of a graph on a sphere all of whose faces have four vertices
Let $G$ be a graph drawn on the sphere such that every face of $G$ has exactly four vertices. Question: can anything be said about the rank of the adjacency matrix of $G$ in terms of other (preferably ...
- 256
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
0
votes
1
answer
123
views
Petersen graph does not have a nowhere-zero 4-flow
I try to prove that the Petersen graph does not have a nowhere-zero 4-flow (i.e., over $\mathbb{Z}_4$), but I don't know how a proof could work...
I'm happy about every hint, thank you in advance!
- 109k
2
votes
1
answer
100
views
Clique number and a special partition
Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that ...
- 23.7k
2
votes
1
answer
226
views
Expanders except for commutativity?
What would you call a graph that is an expander except for commutativity, in the following sense?
Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your ...
- 148k
3
votes
2
answers
2k
views
Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected
I have a two part question:
Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...
4
votes
1
answer
371
views
Looking for a counterexample to a strengthening of the union-closed sets conjecture
[Now crossposted at math.stackexchange]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ ...
- 990
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 23.7k
1
vote
1
answer
298
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
CommunityBot
- 1
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 349
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 349
1
vote
2
answers
386
views
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 5,409
1
vote
0
answers
72
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 349
0
votes
1
answer
82
views
Is there a stiff graph that is not a core?
By a graph, I mean a simple, undirected graph with no loops. A graph homomorphism $f : G \to H$ is a function from the vertexset of $G$ to the vertexset of $H$ such that if $u$ and $v$ are adjacent ...
- 331