**3**

votes

**1**answer

141 views

### Condition(s) for the full autormophism group $\operatorname{Aut}(C(G, S))$ of the Cayley graph of $G$ to be isomorphic to $G$

If $\Gamma = C(G, S)$ is the (undirected) Cayley graph of a finite group $G$ with generating set $S$, then $G \le \operatorname{Aut}(\Gamma)$, the "full" automorphism group of $\Gamma$.
When is ...

**3**

votes

**2**answers

109 views

### Matching polynomials and Ramanujan graphs

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...

**2**

votes

**2**answers

142 views

### Term for vertex connected to every other vertex in a graph

Do you know a good common term for the operation of connecting a new vertex v to every vertex in a graph G (or a term for such vertex v)?
The ones I know give me poor search results:
a nice word ...

**0**

votes

**0**answers

32 views

### Least square problems with binary variables

I want to solve the heat equation $T_t(x,t) = - L_x . T(x,t) + F(x,t)$ in an edge-weighted graph where $L_x = \sum_i x_i e_{ij}$ is weighted Laplacian matrix of the graph. Then I conclude to the ...

**0**

votes

**0**answers

40 views

### Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges.
In particular ...

**8**

votes

**1**answer

166 views

### Is the Cayley graph of Thompson's group isolated in the space of vertex-transitive graphs?

Consider Thompson's group (the one commonly referred to as $T$), which is finitely presentable. Consider the Cayley graph, but then forget the coloring and direction on edges. So now we just have an ...

**7**

votes

**0**answers

64 views

### Approximation of the effective resistance on Cayley graph

Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...

**0**

votes

**0**answers

42 views

### Confusion about reduction counting vertex covers to counting cycle covers

Cross-posted from cstheory
This confuses me.
One easy case of counting is when the
decision problem is in $P$ and there are no solutions.
A lecture show that the problem of counting the number of ...

**5**

votes

**0**answers

101 views

### What's the variance in the Six Degrees model?

Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.
I interpret the punchline as saying that if I start ...

**3**

votes

**1**answer

114 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**6**

votes

**2**answers

164 views

### Geometric dominating set: NP-complete?

Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...

**4**

votes

**2**answers

142 views

### Statistics of strongly connected components in random directed graphs

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for.
...

**4**

votes

**1**answer

76 views

### Are there 2-connected regular graphs whose maximum matching leaves 3 vertices uncovered?

I'd like to use Corollary 5 of a paper by Hell & Kirkpatrick on graph packings to obtain an NP-hardness result. They want a 2-vertex-connected graph $F$ such that every matching in $F$ leaves at ...

**2**

votes

**1**answer

91 views

### When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.
As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...

**1**

vote

**1**answer

98 views

### Proof of closed walk generating function identity

In 'Spectral Conditions for the Reconstructibility of a Graph' Godsil and McKay give a short proof of an identity (Lemma 2.1) that relates the generating function for the number of closed walks ...

**7**

votes

**2**answers

821 views

### Surveys of the items of Erdős' “toolbox”

Could you point out some survey papers and monographs that highlight the kernel of tricks, techniques, and tools that Paul Erdős employed the most in his research work (in particular in graph theory, ...

**4**

votes

**3**answers

99 views

### Linear intersection number and vertex covering number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then ...

**11**

votes

**1**answer

235 views

### Papers about decentralized search and cluster

I just start an independent study about small world network and clusters and I try to find papers about decentralized search and clusters.
Can anyone give me some references? Thanks!
EDIT (David ...

**0**

votes

**0**answers

45 views

### About adjacency matrices of $k-$shift lifts of graphs

I am finding the notation of cyclic lifts of graphs to be very confusing.
Lets say one is looking at a cyclic $k-$lift of a $\vert V \vert$ sized graph.
I would like to understand what is the ...

**15**

votes

**2**answers

401 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

301 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

356 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

255 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

225 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

56 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

98 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

100 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

93 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

104 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

92 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

170 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

66 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

59 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

219 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

142 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

400 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

122 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

116 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

148 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

92 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

142 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

167 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

130 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

157 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

69 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$) ...