# Tagged Questions

**15**

votes

**2**answers

403 views

### Can all unit-distance graphs have their vertices at algebraic integers?

A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...

**0**

votes

**3**answers

303 views

### On independent sets of graph

Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number.
Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality ...

**2**

votes

**0**answers

94 views

### Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...

**10**

votes

**2**answers

357 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

267 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

226 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

60 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

101 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

103 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

44 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

148 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

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

**3**

votes

**0**answers

111 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

94 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

177 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

68 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

60 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

228 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

143 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

411 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

124 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

117 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

154 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

93 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

80 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

145 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

169 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

138 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

158 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

**1**answer

106 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

163 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

150 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

65 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

74 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

75 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)?

**11**

votes

**2**answers

718 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

249 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

201 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

202 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

115 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

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

**5**

votes

**1**answer

170 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

48 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

258 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

108 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

178 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

42 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$ ...