**10**

votes

**2**answers

349 views

### Can a graph be reconstructed from its cycle lengths?

All graphs discussed are finite and simple. The cycle sequence of a graph $G$, denoted $C(G)$, is the nondecreasing sequence of the lengths of all of the cycles in $G$, where cycles are distinguished ...

**6**

votes

**1**answer

249 views

### Infinite graphs isomorphic to their line graph

The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).
There are connected countable graphs that are isomorphic to ...

**6**

votes

**1**answer

222 views

### Induced subgraphs of small strongly regular graphs

Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed ...

**0**

votes

**0**answers

49 views

### Generating alternating cycles on a perfect matching

Given a perfect matching $M$ in a regular bipartite graph $G$, is there an efficient algorithm to randomly generate self-avoiding alternating cycles with uniform distribution? Ideally, such an ...

**0**

votes

**1**answer

91 views

### Graph lifts and representation theory

Is there any connection known between the two?
One can naturally define lifts of graphs by groups like $\mathbb{Z}_k$ and hence I wonder if representation theoretic properties can be used to say ...

**1**

vote

**1**answer

96 views

### Graph classes where finding explicit coloring have certificate that it is minumum

Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.
I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially ...

**2**

votes

**0**answers

42 views

### Counting labelled graphs according to sets of size 3

In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...

**4**

votes

**2**answers

145 views

### Maximum matchings in infinite graphs

For any graph $G=(V,E)$ we define $\mu(G) = \sup\{|M|: M\subseteq E(G) \text{ is a matching}\}$.
Is there a graph $G=(V,E)$ such that for every matching $M\subseteq E$ we have $|M|<\mu(G)$?

**1**

vote

**0**answers

81 views

### Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...

**2**

votes

**0**answers

83 views

### Characterizing graphs with $k$ edge-disjoint minimum diameter spanning trees

Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to $k$ edge-disjoint spanning trees by Frank and Szegõ [3]. ...

**0**

votes

**0**answers

64 views

### When is edge colored circulant isomorphism polynomial?

Don't understand enough group theory, but two papers
appear to give partial results about an open problem.
Edge colored graph isomorphism is isomorphism which
preserves the edge coloring (the ...

**0**

votes

**1**answer

87 views

### When is a $2$-lift of a graph connected? [closed]

Let $\ (V\ E)\ $ be a graph, i.e. $\ E\subseteq\binom V2.\ $ A $2$-lift pattern of a graph is a function $\ e:E\rightarrow\{-1\,\ 1\}.\ $ The induced 2-lift is defined as the graph $\ V\times\{-1\,\ ...

**3**

votes

**2**answers

161 views

### Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph without diagonalizing it. The graphs I am interested in are not regular (but ...

**0**

votes

**0**answers

62 views

### Signed Laplacians and Ramanujan graphs

Given a signing/2-lift matrix $A_s$ of a $d-$regular graph one has the relationship that the ``Signed Laplacian" is $L = d + A_s$. This $L$ is still the same size as the base graph. But the lifted ...

**1**

vote

**1**answer

56 views

### Laplacian spectrum of $2-$lifts of graphs

We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on ...

**1**

vote

**2**answers

177 views

### Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...

**5**

votes

**1**answer

140 views

### How many cospectral graphs available for a given number of nodes?

Two graphs are said to be cospectral if they have same eigenvalues wrt adjacency matrix, Normalised or Signless laplacian matrix. How many graphs has cospectral mates for a given number of nodes? We ...

**10**

votes

**2**answers

391 views

### What is the smallest 4-chromatic graph of girth 5?

It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5?
The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is ...

**0**

votes

**0**answers

119 views

### Solving gradient of an especial heat equation

In my research I came up with a gradient of heat equation on a edge-weighted graph as:
\begin{equation*}
\nabla_w T_t(t,w) + T(t,w) . \nabla_w L_w + L_w . \nabla_w T(t,w) = 0
\end{equation*}
where ...

**3**

votes

**0**answers

108 views

### What mathematical models can analyze and optimize systems based on gossip?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as people gossiping about stuff.
System description:
We have a ...

**3**

votes

**0**answers

134 views

### The Bilu-Linial conjecture and Ramanujan graphs

The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...

**2**

votes

**2**answers

87 views

### Automorphism group of directed complete graph

Given a directed complete graph on $n$ vertices, is there an efficient algorithm for computing its automorphism group? Is there a nontrivial upper bound on the order of its automorphism group? How ...

**0**

votes

**0**answers

75 views

### What is this graph property: number of vertices it takes to see every vertex?

I am wondering what the name is for the following graph property: given a graph $G$ what is the smallest cardinality of $A\subseteq G$ such that every $v\in G$ is connected to some vertex of $A$? I am ...

**0**

votes

**1**answer

135 views

### Are these particular kinds of matrices well known?

Given two positive integers $n$ and $a \leq \frac{n}{2}$ consider a $n \times n$ matrix $A$ such that,
all the diagonal entries are either $a$ or $a+1$
all the non-zero off-diagonal entries are ...

**2**

votes

**1**answer

165 views

### Minimum number of edges to remove to have low degree

I have the following problem (k fixed integer):
Input: Graph G.
Output: Minimum number of edges to remove to G to obtain a graph such that every node has degree at most k.
Do you know the complexity ...

**0**

votes

**0**answers

115 views

### Prove or disprove this upper bound on chromatic number

Let $G$ be a simple connected finite graph and let $v \ge 4$ be the number of vertices, $E$ the number of edges, $\chi(G)$ the chromatic number , $\omega(G)$ the clique number and $\Delta$ the ...

**5**

votes

**0**answers

153 views

### Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices).
A partial $k$-resolution of $G$ is a set of pairwise ...

**1**

vote

**0**answers

64 views

### Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...

**1**

vote

**0**answers

147 views

### Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...

**4**

votes

**1**answer

143 views

### Structure of the stabilizer of a vertex-neighborhood of a vertex-transitive graph

Given a simple, undirected graph and a vertex $v$ of the graph, let $L_v$ denote the set of automorphisms of the graph that fixes the vertex $v$ and each of its neighbors. When the graph is ...

**0**

votes

**0**answers

61 views

### Covering a set in a hypergraph

I'm interested in counting the following. Consider a set $\{v_1,\dots,v_m\}$ of $m$ vertices in the complete $k$-uniform hypergraph on $n$ vertices where $m < k$. I want to know the number of ...

**0**

votes

**0**answers

63 views

### Parallelism degree of a DAG

Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y ...

**1**

vote

**1**answer

66 views

### Spectral radius of a time-varying matrix with strictly positive increment of the matrix's entry

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ being the largest eigenvalue of $A(t)$ and $t$ denotes the time. If $A(t)$ changes over time with each time a ...

**18**

votes

**5**answers

1k views

### Collection of conjectures and open problems in graph theory

Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?

**10**

votes

**2**answers

650 views

### What is a “Ramanujan Graph”?

I noticed an apparent conflict in the definition in literature about what is a "Ramanujan graph, which I was wondering if someone could kindly clarify.
(1)
The Hoory-Linial-Wigderson review on ...

**10**

votes

**1**answer

243 views

### Are there non-trivial graphs that uniquely embed to hypercubes?

The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s ...

**2**

votes

**2**answers

198 views

### Removing subtrees

Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...

**4**

votes

**1**answer

187 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**2**

votes

**1**answer

111 views

### How to construct a graph with arbitrarily large girth and large chromatic number? [closed]

Erdos theorem says it is possible and it is not so easy. What is the general procedure to construct graphs like Grötzsch graph?

**0**

votes

**0**answers

17 views

### Looking to derive bound for modulus of harmonic eigenfunction on weighted graph

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus:
$\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$
and wish to lower ...

**4**

votes

**1**answer

149 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**2**

votes

**0**answers

47 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**4**

votes

**1**answer

252 views

### Endomorphisms and almost all graphs

Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs ...

**1**

vote

**0**answers

58 views

### Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...

**4**

votes

**1**answer

107 views

### Determining the number of hamiltonian paths of $K_n-C_n$

I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...

**2**

votes

**1**answer

175 views

### Edge density of triangle-free graphs

Let $G$ be a finite, simple, loopless graph with $|V(G)|=n$. We define its edge density as $$ed(G) := \frac{|E(G)|}{n \choose 2}.$$
Moreover we set $$d_n := \text{max}\big\{ed(G): G \text{ is a ...

**1**

vote

**0**answers

39 views

### Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...

**7**

votes

**1**answer

168 views

### Universal graph homomorphisms

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such ...

**17**

votes

**1**answer

296 views

### Lens spaces and generalized Petersen graphs

Recently I came across this mathoverflow question, in which the number of homeomorphism classes of 3-dimensional lens spaces $L(p, q)$ is computed as a function of $p$. Using the OEIS, I found a ...

**9**

votes

**1**answer

348 views

### Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality?
Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has
$$
\int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) ...