Algebraic methods in Graph Theory; the linear algebra method, graph homomorphisms, group theoretic methods (for example Cayley graphs), and graph invariants. For graph eigenvalue problems use the spectral-graph-theory tag. For strongly regular graphs use the strongly-regular-graph tag. For ...

learn more… | top users | synonyms

-2
votes
0answers
30 views

Graph Isomorphism of Graphs that are not Locally Triangle-Free

What is the computational complexity of graph isomorphism problem for graph-class $\mathcal{G}$ that excludes graphs which are locally triangle-free ? Is this $\mathcal{G}$ class included in any ...
3
votes
2answers
133 views

Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of ...
6
votes
2answers
477 views

A question about (unicity of certain cycles in a Cayley graph of a) symmetric group

Let $S=\{(1,2),(1,2,3,\ldots,n),(1,2,3,\ldots,n)^{-1}=(1,n\ldots,2)\}$ be a subset of the symmetric group $S_n$. We know that $(1,2,\ldots,n)(1,2)=(2,3,\ldots,n)$, and thus ...
3
votes
3answers
149 views

Graphs cospectral with Cayley graphs

Let $G$ be a Cayley graph, and $H$ a graph cospectral with $G$. Must $H$ be a Cayley graph? Does a counterexample exist? If $G$ is a circulant graph, does a counterexample exist?
0
votes
0answers
49 views

normal sets and conjugate generating sets of $S_n$

In this arXiv paper (p. 13), Steinhardt defines a normal set in $S_n$ as follows: Definition: A split set of more than two cycles generating $S_n$ is said to be normal if any element is adjacent to ...
6
votes
3answers
243 views

Numerical invariants for a graph or its complement that are bounded by some constant

I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but ...
0
votes
0answers
111 views

Ramanujan graphs and stable real polynomials

I have a problem with the lemma 6.5 and the theorems 5.1, 6.6 in the paper of Adam Marcus, Daniel Spielman and Nikhil Srivastava. http://arxiv.org/pdf/1304.4132.pdf I do not understand how they use ...
1
vote
0answers
35 views

Atomic parts of lexicographic products of vertex-transitive graphs

Suppose $H_1$ and $H_2$ are connected, vertex-transitive graphs, $H_1$ is not the complete graph, and $|V(H_2)| \ge 2$. Then, the lexigraphic product $G=H_1 \circ H_2$ is vertex-transitive, $0 < ...
3
votes
1answer
120 views

Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...
0
votes
1answer
42 views

Number of $k$-walks containing a vertex in an unweighted multigraph

Let $G = (V,E,W)$ be a weighted graph, where each edge $e = (v_i,v_j)$ has weight $w_{ij} \in \mathbb Z^+ \cup \{0\}$. By replacing $e$ with $w_{ij}$ copies of unweighted multiedges, a weighted graph ...
3
votes
0answers
101 views

The degree/diameter problem for even girth graphs starting with upper bound

I posted this on stackexchange but due to a lack of response there I am posting here. Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define ...
6
votes
3answers
254 views

Generating (or availability of) large strongly regular graphs

Are there collections of already generated large strongly regular graphs available to download? By large I mean $n \geq 200$ where $n$ is the number of vertices. I found Ted Spence's page on srgs, ...
5
votes
0answers
99 views

Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
6
votes
1answer
128 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
0
votes
0answers
153 views

Cayley graphs with special subgraphs and some related problems

I asked some questions about finite Cayley graphs with special type of subgraphs which has been answered by Dear Prof. Godsil. It can be seen in the MO page with address: Cayley graphs and its ...
0
votes
1answer
113 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
1answer
124 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
1answer
224 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 ...
5
votes
2answers
226 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 ...
4
votes
0answers
176 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
1answer
200 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
1answer
296 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
2answers
239 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
2answers
265 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
1answer
73 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
4answers
247 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
2answers
274 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
0answers
101 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
3answers
321 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
1answer
225 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
1answer
241 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
0answers
297 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
1answer
395 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
0answers
235 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
0answers
115 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
2answers
147 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
1answer
212 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
0answers
58 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 ...
2
votes
1answer
357 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
5answers
4k 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
1answer
151 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
1answer
578 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
1answer
413 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
2answers
191 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 ...
5
votes
3answers
479 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
2answers
336 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
1answer
236 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 ...
2
votes
1answer
159 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
1answer
255 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
1answer
291 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 ...