The algebraic-graph-theory tag has no wiki summary.

**0**

votes

**1**answer

89 views

### Graph automorphisms that preserve independent sets [closed]

Let $G=(V,E)$ be a graph and $\mathrm{Ind}(G)$ be the collection of its independent sets.
We call a graph automorphism $f:V \to V$ of $G$ good if it is non-trivial and ...

**1**

vote

**1**answer

86 views

### Linear algebra formulation for colored node graph isomorphism

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.)
Some basic definitions for completeness:
Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...

**5**

votes

**1**answer

185 views

### When is the direct product of two graph cores itself a core?

A graph homomorphism $f$ is a function $f : V(X) \to V(Y)$ such that if $uv \in E(X)$, then $f(u)f(v) \in E(Y)$. If such an $f$ exists, write $X \to Y$. $X$ and $Y$ are hom-equivalent if $X \to Y$ and ...

**0**

votes

**0**answers

39 views

### Is there any analytically expressible choice of disjoint perfect matchings?

Consider being given a $d-$regular $(n,n)$-bipartite graph. We know that its edge set decomposes into $d$ disjoint perfect matchings. I want to know if there is a analytic way to pick such a ...

**5**

votes

**2**answers

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

**5**

votes

**0**answers

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

**4**

votes

**1**answer

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

**6**

votes

**1**answer

267 views

### Do perfect matching(s) have signatures in the graph eigenvalues?

If the edges of a bipartite graph are such that they can be seen as a disjoint union of perfect matchings then will this somehow reflect in the eigenvalues of the Laplacian?
It would be helpful to ...

**4**

votes

**2**answers

164 views

### Graphs whose degree vectors coincide for all powers of their adjacency matrices

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.
Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...

**9**

votes

**2**answers

244 views

### Vertex-primitive graphs with two vertices having almost the same neighbourhood

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$
Question: Is it true that $\Gamma$ must either be a complete graph or have ...

**0**

votes

**1**answer

57 views

### edge transitivity and edge deletion

Let G be a graph which has the following properties:
1) For every $e_1,e_2 \notin E(G)$, $G \cup e_1 \cong G \cup e_2$
2) For every $e_1,e_2 \in E(G)$, $G\setminus e_1 \cong G\setminus e_2$
i.e. ...

**0**

votes

**4**answers

177 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**6**

votes

**2**answers

229 views

### adjacency matrix of a graph and lines on quartic surfaces

Suppose you are given a smooth quartic surface $X$ in $\mathbb P^3$. I would like to find an upper bound for the number of lines on $X$ in the case that there is no plane intersecting the curves in ...

**2**

votes

**0**answers

90 views

### Triple Transitive Graphs

In the paper A Note on Triple Transitive Graphs, Cameron gives an almost-complete determination of triple transitive graphs with girth greater than $3$. In the remark at the end he says:
"If, as ...

**12**

votes

**3**answers

308 views

### How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...

**1**

vote

**1**answer

151 views

### almost equitable partitions and spectra

If a graph $G$ has an equitable partition, then its charachteristic polynomial (for the adjacency matrix) has a divisor that can be seen as the characteristic polynomial (for the adjacency matrix) of ...

**2**

votes

**1**answer

222 views

### Upper bound on the number of vertex transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?

**2**

votes

**0**answers

247 views

### On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard.
Assume we talk only about classes of undirected ...

**6**

votes

**1**answer

366 views

### On Turan's theorem

Turan's theorem provides minimum number of edges of a graph on $n$ vertices to surely contain a clique of a prescribed size. This has been generalized to regular graphs.
What additional ...

**5**

votes

**0**answers

189 views

### Graphs with many positive eigenvalues of their distance matrix

Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.
We call a graph $G$ optimistic if ...

**1**

vote

**0**answers

107 views

### A traveling time problem

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$
...

**4**

votes

**2**answers

137 views

### Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...

**0**

votes

**1**answer

209 views

### A question on graphs

Do there exist a family of graphs with the property:
$$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes \bar{G}}}\right)\right| = O(\log(N_{G}))$$
where $G$ is the ...

**0**

votes

**0**answers

56 views

### vertex transitive graphs with 4p vertices with an imprimitivity block of length p and lexicographic product

Let $\Gamma$ be a vertex transitive graph with $4p$ vertices, where $p$ is an odd prime. Let $\Delta$ be an imprimitive block of length $p$ for the automorphism group of the graph. How can I prove ...

**1**

vote

**1**answer

303 views

### tutte's kirchhoff matrix and the matrix-tree theorem for digraphs

In his books, Tutte tells often of how he and his friends in Cambridge introduced a theory of non-symmetric electricity. His tales are always amusing and enjoyable, but often lack precise references; ...

**1**

vote

**5**answers

3k views

### Graduate Schools for Graph Theory [closed]

I am a rising senior in a small liberal arts college, and I was wondering if anyone could suggest me good graduate schools for graph theory. My only exposure to graph theory has been the intro graph ...

**4**

votes

**1**answer

145 views

### Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$.
Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...

**12**

votes

**1**answer

538 views

### Tutte polynomials, graph complements and degree sequences

Harary and Akiyama asked whether there exists a non self-complementary (SC) graph $G$ having the same chromatic polynomial as its complement.
It was later shown that there indeed exist such graphs ...

**1**

vote

**1**answer

324 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...

**1**

vote

**2**answers

182 views

### signs of eigenvalues

Let $\Gamma$ be a multiple edge free (di)graph (with or without loop). Let $A$ be its adjacency matrix. It is clear that if $\lambda^2$ is an eigenvalue of $A^2$, then $\lambda$
or $-\lambda$ is an ...

**4**

votes

**3**answers

415 views

### automorphisms of graphs and finite permutation groups

I am interested in automorphisms of graphs and in using tools from permutation groups (especially such as in Wielandt's text on finite permutation groups, which I have been studying). What are some ...

**2**

votes

**2**answers

264 views

### Is there any relation between automorphism group of a Cayley graph over a group and over its subgroup?

Let $\Gamma=Cay(G,S)$ be a Cayley graph over a group $G$, $H$ be a proper subgroup of $G$ and $\Sigma=Cay(H,T)$ where $S$ and $T$ are inversed-closed subsets of $G$ and $H$ not containing idendity, ...

**2**

votes

**1**answer

205 views

### What are some interesting almost equitable partitions which are not equitable?

There have been questions lately about almost equitable partitions in graphs, for example this one which provides the definition.) Every equitable partition is almost equitable. The converse is true ...

**1**

vote

**1**answer

149 views

### simple graphs of degree 16 with a semiregular normal subgroup isomorphic to the quaternion group $Q_8$

Is there any simple graph $\Gamma$ with 16 vertices with full automorphism group $G$ such that $H\cong Q_8$ be a semiregular normal subgroup of $G$?

**2**

votes

**1**answer

232 views

### Strongly regular cayley graphs

Let $G$ and $Cay(A,S)$ be strongly regular graphs with the same parameters. Is it true that $G$ is a cayley graph?

**0**

votes

**1**answer

273 views

### vertex-transitive graphs of order 10 with full automorphism group $A_5$ or $S_5$.

By a well-known result we know that a simply primitive permutation group of degree $2p$ where $p$ is a prime is $A_5$ or $S_5$ acting on 2-subsets of $\{1,\ldots,5\}$. The group has rank 3 and the ...

**0**

votes

**1**answer

69 views

### imprimitive 2-blocks in connected Cayley (di)graphs of order twice a prime

Let $\Gamma=Cay(G,S)$ be a connected Cayley (di)graph over a group of order twice a prime and $\Sigma$ be a complete system of 2-blocks for $Aut(\Gamma)$. Let $K$ be the kernel of the action of ...

**0**

votes

**2**answers

214 views

### Semiregular subgroups of automorphism group of cayley graphs

Let $\Gamma$ be a Cayley graph over group $K$ and $H$ be a semiregular subgroup of $Aut(\Gamma)$ with two orbits. Then $|K|=2|H|$. Is there any other relation between $H$ and $K$ in general? What ...

**4**

votes

**1**answer

628 views

### Algebraic characterisation of directed acyclic graphs

Any characterization based on the adjacency matrix for directed acyclic graphs (DAG)?
An undirected graph could be simply characterized by saying that its adjacency matrix is symmetric. What about a ...

**6**

votes

**1**answer

400 views

### (The) missing Moore graph(s) - uniqueness

In the related literature one often sees the phrase "The missing Moore graph" which (to me) tacitly implies that the missing Moore graph (if exists) is unique.
Is there a result of this type or is or ...

**8**

votes

**1**answer

440 views

### Bicycles and spanning trees of graphs

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the ...

**4**

votes

**2**answers

556 views

### Neat results from algebraic graph theory

Studying algebraic graph theory, I've stumbled across a wide range of results that I found pretty stunning and also useful. I'd like to share them here and ask for your favorite result from this area?
...

**4**

votes

**1**answer

279 views

### Graphs which are “distance-regular” with respect to a vertex (but not distance-regular)

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all ...

**7**

votes

**4**answers

1k views

### Cayley graphs and its subgraphs

I have two questions about Cayley graphs. Any answers will be appreciate.
1) Do we have any Cayley graph that has Petersen graph as its induced subgraph?
2) Suppose $Cay(G,S)$ be a Cayley graph that ...

**6**

votes

**3**answers

1k views

### Eigenvectors and partitions of graphs

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ ...

**5**

votes

**1**answer

931 views

### Has anyone seen this graph?

I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone ...

**3**

votes

**3**answers

500 views

### Is this statement about the real edge space of a graph known or trivial?

The statement is:
($u$ is a fixed node in a fixed graph $G$)
$G$ is 3-connected
if and only if
the set of u-cycles span $\mathbb{R}^{E(G)}$.
A u-cycle is a simple (no vertex repetitions) cycle in G ...

**3**

votes

**2**answers

394 views

### Lovasz function equality - combinatoric graph theory.

Hello everyone,
I was wondering how to prove the following equality:
$\theta(G+H)=\theta(G)+\theta(H)$
where $G$ and $H$ are graphs and $\theta$ is the Lovasz Theta function.
correction:
I ...

**2**

votes

**1**answer

208 views

### Graphs of order n with a Laplacian eigenvalue of multiplicity n-1.

I suspect this could be an easy one but I am not an expert in algebraic graph theory.
Let $Q(G)$ define the Laplacian matrix for a simple graph $G$. It is well known that n is an eigenvalue of ...

**2**

votes

**0**answers

223 views

### Group of local complementation as a coxeter group

Can the group generated by local complementations, ${lc_i|i=1,\cdots,n}$ on simple graphs on $n$ vertices, be categorized as a coxeter group? After all these obey:
\begin{equation}
\langle lc_i| ...