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, ...

learn more… | top users | synonyms

0
votes
0answers
22 views

1-factorizations of complete multigraphs

When is it possible to find a 1-factorization of the complete multigraph $\lambda K_{2k}$ in which any two 1-factors have at most 1 edge in common? In particular, I am interested in whether such a ...
1
vote
3answers
131 views

On number of perfect matchings

Consider $2n$ vertex balanced bipartite graph. If total number of edges is $n^2$ then we have $n!$ perfect matchings. Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite ...
1
vote
1answer
53 views

Is there any digraph data set that gives all directed graphs satisfying certain requirements?

I'm looking for a digraph dataset that can return all directed graphs satisfying certain requirements. Following are some examples: All tournament with 12 vertices; All connected digraphs with 10 ...
4
votes
2answers
245 views

Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be ...
2
votes
0answers
78 views

Regularity for a bipartite graph

Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that: 1) degree of every vertex is not greater then $2^t$ 2) number of all edges is greater than $2^{n +t - O(\log ...
0
votes
1answer
55 views

Long term behavior of a certain discrete time dynamical system on graphs

Consider the graph $(V,E)$ with vertex set $V=\{v_1,...,v_n\}$ and edge set $E\subset V\times V$. Further, assume that $\forall v_i\in V, (v_i,v_i)\in E$. Assume that each vertex has an ...
1
vote
1answer
101 views

Graph Isomorphism for Triangle Free graph

Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs? Anything close to the subject will help and of course, I have searched Google.
3
votes
1answer
98 views

Covering a graph by trees with depth constraint

Given a graph $G$ and a depth constraint $h$, my question is: what is the complexity to find a tree cover of $G$, denoted as $T=\{T_1, T_2, ..., T_n\}$. For each $T_i$, its depth(height) is no larger ...
1
vote
0answers
44 views

Largest number of perfect matchings in bounded genus graphs

What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?
0
votes
0answers
28 views

Similarity metric for labelled weighted graph/minimum spanning tree

I'm looking for a metric to measure similarity of minimum spanning trees of labelled weighted graphs. Each entity to compare has the same nodes (number of nodes and labels identical) but (unlabelled) ...
1
vote
0answers
42 views

Influence of independent variables on boolean functions?

Suppose a simple connected graph $G$ where its vertices are assumed to be independent. An event with uncertainty corresponds to each vertex. My instructor guides me that even though the vertices ...
2
votes
0answers
57 views

When is the graph of cliques isomorphic to the graph itself?

Given a graph $G$ and the set $C_k(G)$ of the $k$-cliques in $G$, one can build a clique graph $H$ whose vertices $c_i\in C_k(G)$ are connected if the vertex sets of $c_i$ and $c_j$ have an ...
13
votes
2answers
369 views

Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
3
votes
1answer
88 views

A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
5
votes
2answers
126 views

Finite graph colorings without symmetries

Let $G$ be a connected finite simple graph with vertex set $V$, $F$ a finite set and let $\Delta(G)$ denote the degree of $G$, i.e. $\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring ...
4
votes
3answers
176 views

Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this: ...
1
vote
1answer
153 views

What does the higher coefficients of ihara zeta function reveal?

Assume we have a graph $G=(V,E)$. The ihara zeta function $Z(G,u)$ is of form $$\frac1{\displaystyle\sum_{i=0}^{2|E|}c_iu^i}$$ A graph which has $|E|$ edges cannot have a simple cycle of length ...
1
vote
0answers
48 views

How to count the number of shortest paths in a 2x2 grid? [closed]

Say that we have a 2x2 regular grid or network. We label the nodes 0 to 3 row-wise. Then, for each node, we want to compute the number of shortest paths that pass through them. I have a Python code ...
1
vote
0answers
36 views

Infinite graphs with number of common neighbors given for each pair of vertices

This is a follow-up to this question. For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. If $G=(V,E)$ is a simple undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in ...
1
vote
0answers
62 views

Number of rooted spanning forests

Let $G$ be a connected simple graph, and identify two vertices $s$ and $t$. Let $\tau(G)$ be the number of spanning trees of $G$, and let $f(G)$ be the number of spanning forests of $G$ with $2$ ...
1
vote
1answer
75 views
7
votes
1answer
126 views

Can the graph removal lemma be proved directly from the triangle removal lemma?

The Triangle Removal Lemma states that any graph with $o(n^3)$ triangles can be made triangle-free by removing only $o(n^2)$ edges. More generally, the Graph Removal Lemma states that for any graph ...
0
votes
1answer
129 views

Stable marriages for infinite bipartite graphs

Short and informal version: Does the stable marriage problem have a solution if there are $\kappa$ men and $\kappa$ women for any cardinal $\kappa \geq \aleph_0$? Long and formal version: Let ...
-2
votes
1answer
61 views

Splitting the vertices of undirected graphs into 2 sparse sets

(A version of this question for undirected graphs.) Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set $$ N(v) := \{x\in V: \{x,v\}\in E\}. $$ Is it possible to find a ...
15
votes
5answers
470 views

Cayley graphs of $A_n.$

Consider the Cayley graphs of $A_n,$ with respect to the generating set of all $3$-cycles. Their properties must be quite well-known, but sadly not to me. For example: what is its diameter? Is it an ...
1
vote
1answer
76 views

many 5-list colorings

If a graph is 4-list-colorable, then it is easy to see that it has exponentially many 5-list colorings. This is the first sentence in [Exponentially many 5-list-colorings of planar graphs,JCTB,97 ...
1
vote
1answer
70 views

Partitioning finite directed graphs into 3 “incoming-sparse” sets

Let $G=(V,E)$ be a directed graph. For $v\in V$ set $\text{In}(v)=\{x\in V: (x,v)\in E\}$. Is it possible to find a partition $P_1,P_2,P_3$ of $V$ such that for every $P_i$ and every vertex $v\in ...
7
votes
3answers
292 views

A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
1
vote
0answers
42 views

How to estimate the size of balanced biclique in random bipartite graph?

We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...
1
vote
0answers
59 views

Equivalence between bipartite undirected graph and arbitrary directed graph

Let the adjacency matrix of an undirected bipartite graph be $A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$ where B is called the biadjacency matrix. Now, by instead interpreting B as ...
-2
votes
1answer
61 views

Degrees and common neighbors

For any simple, finite, undirected graph $G=(V,E)$ and $v\in V$ let $N(v) = \{w\in V:\{v,w\}\in E\}$. Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex ...
-6
votes
1answer
94 views

Do degrees determine the chromatic number?

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = ...
5
votes
0answers
115 views

Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time: $$ \exp(O(\log^c n)) $$ where $n$ is the number of vertices. What is the best bound we have for $c$? (The ...
4
votes
2answers
200 views

Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...
3
votes
1answer
74 views

Let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?

As the title says, let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph? I suspect the most likely counterexample would be $|S|=1$.
5
votes
2answers
124 views

“Common-neighbor-regular” graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$. We say that $G$ is $k$-common-neighbor-regular if for all $v\neq w\in V$ we have $|N(v)\cap ...
3
votes
1answer
83 views

Tournament whose large subtournaments contain no automorphism

For sufficiently large $n$, it is known that most tournaments of size $n$ contains no nontrivial automorphism, though I forgot the reference. For sufficiently large $n$, does there always exist a ...
4
votes
1answer
123 views

Representing a graph's vertices as linear combinations of paths

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...
5
votes
1answer
192 views

Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between ...
0
votes
0answers
57 views

Tight bound of Turan number for K_{1,t,t}?

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t. The motivation is that we now ...
0
votes
0answers
35 views

Question about number of faces for regular graphs

I came upon the following problem. Consider a regular 3-graph with faces of degree $2, 3, 4, 5$, 4-graph and faces of degree $2, 3$ and 5-graph with faces of degree $2, 3$. Are there any such graphs ...
3
votes
1answer
94 views

Menger's Theorem for planar triangulations

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...
4
votes
1answer
81 views

The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$

For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$ Where is $a(n)$ discussed in the literature? Is the exact value ...
2
votes
1answer
116 views

Removing cycles in a directed graph by swapping edges orientation

I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v_i$ and $E$ (directed) edges $e_j$. I know that if an edge $e_k = (v_i, v_j)$ is in the graph, then the opposite ...
0
votes
0answers
25 views

A measurement for vertex- and edge failure sensitivity

I want to have a metric that helps me judge how independent different paths in one graph are. So here are my assumptions: A graph consists of a set of vertices ($V$) and edges ($E$). A path ...
1
vote
0answers
99 views

Extending continuous functions from $\partial X$ to $X\cup \partial X$

Consider a proper geodesic hyperbolic space $X$ (in the sense of Gromov). Let $\partial X$ be its Gromov boundary. Consider a complex-valued continuous function on the boundary $f\colon\partial ...
0
votes
1answer
89 views

Topology on $\omega\times\omega$ such that topologically connected equals graph-connected

For any set $X$ we define $[X]^2 =\big\{\{a,b\}: a, b \in X\text{ and }a\neq b\big\}$. Let $$E = \big\{\{(a_1, a_2), (b_1, b_2)\}\in[\omega\times\omega]^2: |a_i-b_i| = 1\text{ for some } ...
0
votes
0answers
35 views

For which matrices deciding permutation similarity is polynomial?

Q1 For which matrices deciding permutation similarity is polynomial? It is not easier than graph isomorphism (and very likely is equivalent to it). If necessary, assume the entries are ...
0
votes
0answers
39 views

Is the Hadwiger number reconstructible?

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...
0
votes
1answer
110 views

“Reduce-by-1”-isomorphic graphs

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...