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

1
vote
1answer
86 views

Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...
3
votes
1answer
61 views

Alternative parallel paths

Parallel strings which connect points $x_1,\dots, x_n$ with points $y_1,\dots, y_n$, are sewn with an additional string. The union of these $n+1$ strings is considered a framed graph (we remember ...
1
vote
1answer
65 views

Size of connected components of a graph via its spectrum

I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is: Is there a way to understand the size of each connected ...
7
votes
1answer
237 views

Choosing two-colorable subgraph in a triangulation

Consider a planar graph which is a triangulation. Is it possible to find a two-colorable subgraph which has common edge with every face of our graph? It is known that such spanning tree not always ...
0
votes
2answers
58 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...
6
votes
1answer
67 views

Which graphs embedded in surfaces have symmetries acting transitively on vertex-edge flags?

A vertex-edge flag in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of ...
2
votes
1answer
140 views

Self-containing trees

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...
2
votes
0answers
67 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...
1
vote
0answers
65 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph. Is there an efficient ...
0
votes
0answers
65 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 ...
3
votes
1answer
92 views

chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and ...
-1
votes
1answer
91 views

Subgraphs of $\mathbb{R}^2$ in the Hadwiger-Nelson problem

In the setting of the Hadwiger-Nelson problem, two points of $\mathbb{R}^2$ form an edge if and only if their distance is $1$. The resulting graph $G$ has chromatic number $\chi(G)\in \{4,5,6,7\}$ and ...
0
votes
0answers
46 views

Factor group lemma [closed]

I have seen the following statement in http://www.sciencedirect.com/science/article/pii/0012365X84900104 [Page 294, part 2.2], but I cannot understand why "then $\mid N\mid *[a_i: 1\leq i\leq n]$ is ...
1
vote
1answer
54 views

Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$? I am most interested in $d\leq3$ and $g=0$.
4
votes
1answer
165 views

exact definition of Fiedler vector

For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as $$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$ where the corresponding ...
4
votes
2answers
171 views

Non-Cayley expander graphs

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows: Are all expander regular graphs are Cayley, or there is a special ...
1
vote
0answers
22 views

Expected number of perfect matchings in bounded degree bipartite graphs

Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$. What is the expected number of perfect matching a graph in $\mathcal ...
1
vote
0answers
45 views

A centralised website for computational attemps in graph theory and metric geometry?

The set of questions below stems from this question. 1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph ...
0
votes
0answers
20 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
110 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
49 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 ...
3
votes
1answer
90 views

Number of perfect matchings of bipartite graphs

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
75 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
53 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 ...
0
votes
1answer
91 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 ...
0
votes
0answers
41 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
21 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
38 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
56 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
356 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
86 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
119 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
0answers
45 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
150 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
44 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
34 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
59 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
71 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
125 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
58 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
460 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
73 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 ...
0
votes
1answer
63 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 ...
6
votes
3answers
218 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
41 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
58 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
92 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) = ...