Studying graphs using algebra (for example, linear algebra and abstract algebra) as a tool.

learn more… | top users | synonyms

0
votes
1answer
43 views

Can a triangle free graph represent a Group?

Some facts are- Group can be represented by a graph. Quasi Group can be represented by Latin Square matrix, thus by a Latin Square graph. Group Isomorphism $\leq_p$ Graph Isomorphism. Under this ...
0
votes
0answers
13 views

Vertex-transitivity of the automorphism group of a digraph

I am trying to understand the theorem 3 of Cycles in graphs and groups by Kantor. Theorem $3$ If $G$ is a vertex-transitive group of automorphisms of a digraph $\Gamma$ with outdegree $d \ge 1$, ...
1
vote
1answer
31 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
0
votes
1answer
18 views

Spectrum of Line graph of regular graph

Definition: Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows: -The vertices of $L(G)$ are the edges of $G$ -Two vertices of $L(G)$ are adjacent iff their corresponding ...
1
vote
1answer
29 views

On the multiplicity of the eigenvalue 0 of the adjacency matrix?

Preliminaries: -Laplacian matrix of graph $G$ is defined as follows: $$L=D-A $$ where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. -The algebraic connectivity of a graph ...
1
vote
1answer
76 views

In a bipartite graph, every isometric path is a retract.

I know this is true because I see it used in a few papers I am using for a project, but I can't find a solid proof. I have tried some examples to try and figure out how to define my homomorphism but ...
1
vote
0answers
13 views

Is there an analogue of Frucht's theorem for sandpile groups?

In other words, is it the case that for every abelian group $G$, there exists a graph $H$ such that the sandpile group of $H$ is isomorphic to $G$? If not, is the truth of falsity of this still an ...
3
votes
2answers
56 views

Relation between Automorphism group of a graph and its subgraph

Let $G$ be a graph on $r$ vertices $\{1,2,\ldots,r\}$. Further denote $H$ to be the sub-graph of $G$ induced by the vertices $\{1,2,\ldots,(r-1)\}$. Denote $Aut(G)$ and $Aut(H)$ to be the automorphism ...
2
votes
1answer
26 views

Prove Cycle Graphs are never hyper-energetic.

The energy of a graph G, is defined as $$\varepsilon(G)=\sum_{i=1}^{n}\left|\lambda_i\right|$$ where $\lambda_i$ are the eigenvalues associated with the adjacency matrix of the Graph. The energy of a ...
0
votes
1answer
27 views

Number of regular tournaments

A regular tournament is a tournament where each player has the same number of wins. Since each player plays $n-1$ games, a regular tournament must have an odd number of players. My question is - 'how ...
4
votes
2answers
40 views

Geometric intuition of graph Laplacian matrices

I am reading about Laplacian matrices for the first time and struggling to gain intuition as to why they are so useful. Could anyone provide insight as to the geometric significance of the Laplacian ...
0
votes
0answers
21 views

Procedure to construct a map from the automorphism group of a graph to the natural permutation representation

Let $\Gamma$ be a graph with $n$ vertices. Let $\varphi_\Gamma$ be the map from the symmetric group $S_n$ to the space of natural permutation representation $\text{Mat} \left(n, \mathbb{C}\right)$ ...
1
vote
1answer
20 views

Chromatic number of graph obtained by removing set of edges from complete graph

Consider the complete graph on n vertices $S = (V, E)$ and let $K$ be a subset of $E$. If $k$ is the size of the maximal set of independent edges (edges with no common endpoints) in $K$, is the ...
0
votes
1answer
40 views

The definition of the number of ends for a locally finite graph

Here I am wonder what's the definition in terms of vector spaces over Z2, and how to show it's equivalent to other definitions.
0
votes
0answers
20 views

Difference between reflexive and irreflexive graph homomorphisms

I'm reading "Graphs and Homomorphisms" by Hell and Nesetril. Now, Assume G is a graph that could be defined reflexively or irreflexively (so a simple graph). So it has "two versions", if you will. ...
0
votes
0answers
26 views

Prove the lemma on the complement of a strongly regular graph with parameters $ \lbrace n, k,a,c \rbrace $

There is a lemma in the book of Algebraic Graph theory by Chris Godsil is stated as follows The complement of a strongly regular graph is also strongly regular To prove this I followed the following ...
0
votes
1answer
32 views

Prove that the invariant subspace contains eigenvectors of a real symmetric matrix

There is a lemma which has been stated by Chris Godsil in one of his books as follows Let A be an n by n real symmetric matrix. If U is a nonzero A-invariant subspace of $ \mathbb{R} ^{n} $, then U ...
2
votes
0answers
190 views

Sifting Technique : Construction of Isomorphism from sets of Local Isomorphism(Graph Isomorphism)

Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set). ...
4
votes
1answer
101 views

Spectral radius of “almost” regular graph ?!

The answer to this question could be trivial. The Graph Let $G$ be graph formed of two $d$-regular connected components. That is, $G= H_1\cup H_2$, where $H_1$, and $H_2$ are $d$-regular and ...
5
votes
1answer
83 views

Permutation acting on Edges induced by Permutation acting on Vertices

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann Let $X = (V,E)$ be a graph with vertex set $ V = \{1,2..... n \} $. The automorphism group $Aut(X)$ of $X$ is a subgroup of ...
1
vote
0answers
35 views

Merging two nodes in a directed graph with transitions

Let's say I have $M=\begin{bmatrix}1&2&1\\ 4&2&0 \\ 1& 1& 1\end{bmatrix}$, a $3\times3$ matrix which is the transition matrix or adjacency matrix of a $3$-node graph. I would ...
3
votes
1answer
52 views

How does an automorphism of vertices stabilize edges?

How an automorphism of vertices stabilizes edges ? There are some permutations which acts on vertices and edges at the same time. For example, $\pi=(24)$(an automorphism) permutes or switches ...
0
votes
1answer
44 views

Subgraph of integral graph is also integral??

Background: An integral graph is a graph whose spectrum consists entirely of integers (see [1]). Example: Complete graph $K_n$, since spectrum$(K_n) = (n-1,-1,\ldots,-1)$ Question Is the induced ...
3
votes
1answer
35 views

Number of Automorphism (based on Isomorphism)

$X, X'$ be two connected graphs and let $Z$ be there $Disjoint$ union. $D=Aut(X) \times Aut(X')$ . How does $|D|< |Aut(Z)|$ if and only if $X \simeq X'$ ? An example would be helpful. In ...
-1
votes
1answer
37 views

Asymptotic enumeration of regular graphs

I have been following a few papers on the asymptotic enumeration of $r$-regular graphs of $n$ vertices, $L_r$. According to Random Graphs, $L_r = L_n \sim \sqrt{2} e^{- \frac{\left(r^2 - ...
11
votes
5answers
585 views

Applications of graph theory to algebra?

Seeing as graphs model relations and algebra is essentially entirely based on relations, one would think that the two fields would inform each other. I know that algebra has many applications to graph ...
1
vote
0answers
51 views

On the eigenvalues of bipartite graph?

Definition Let $G=U\cup V$ is bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. The complete bipartite graph denoted by $K_{p,q}$ is bipartite graph where every ...
1
vote
1answer
43 views

MST, Cut in Graph, Some Claims?

I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows: Which of the following Claims is True about MST of Simple, ...
1
vote
1answer
48 views

I don't understand how Kirchhoff's Theorem can be true

Kirchhoff's Matrix-Tree theorem states that the number of spanning trees of a graph G is equal to any cofactor of its Laplacian matrix. Wouldn't this imply that all cofactors of a Laplacian matrix ...
1
vote
0answers
22 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
4
votes
1answer
123 views

How to get the directed line graph of the complete digraph?

When we replace every edge of the complete graph $K_N$ by a pair of directed edges, we get a complete directed graph, the Complete DiGraph $DK_N$ . Let $DL_{N}$ be directed line graph of the complete ...
2
votes
1answer
66 views

Kernel of a map in Graph Theory (toric ideals)

If we have an $n$-cycle with edges $e_1 =\{x_1,x_2 \}, e_2 = \{x_2, x_3 \},\dots, e_n = \{x_n,x_1\}$ with a $K-$algebra homomorphism $\phi: k[e_1,\dots, e_n] \to k[x_1,\dots, x_n]$ defined by ...
0
votes
0answers
24 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
31 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
1
vote
0answers
33 views

Is class of graphs with eigenvalue $1$ of any particular importance?

Are graphs with eigenvalue $1$ of multiplicity more than $1$, important one? Please guide me to any book or article discussing such graphs.
0
votes
0answers
11 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
2
votes
1answer
102 views

The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
4
votes
3answers
158 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
0
votes
0answers
19 views

Hamioltonian Circuit of Planar Graph of Order $2^n$

$G$ is a planar graph of order(= number of vertices) $2^n$. Questions: When $G$ has a Hamiltonian Circuit? Is there a polynomial or quasi polynomial time algorithm to decide whether $G$ has a ...
0
votes
0answers
36 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
0
votes
0answers
17 views

My question is about Cayley graphs where the Cayley set is any set of transpositions.

I want to show that if $S$ is any subset of $Sym(n)$ such that $S$ contains only transpositions, then the Cayley graph $X=Cay(Sym(n), S)$ is bipartite. I have figured out that the vertices in $X$ ...
2
votes
0answers
137 views

Is there matrix representation of the line graph operator?

I had the need to calculate the adjacency matrix $L$ of the line graph of a certain planar $k$-regular graphs $G(n,e)$ ( $n$ vertices and $e=\frac k2 n$ edges) given its adjacency matrix $A_G$. Here I ...
0
votes
0answers
20 views

Chromatic polynomial of simple graph

Suppose I know the chromatic polynomial $P(G, \lambda)$ of the graph $G$. Can we express the chromatic polynomial of the graph $G'$ in terms of $P(G, \lambda)$ and $\lambda$? I have tried to ...
1
vote
0answers
26 views

Pseudo vertex-transitive graphs

I'm investigating finite, simple graphs with the following property: For each degree $d$ of $G$, the subgraph induced on all vertices of degree $d$ is vertex transitive. In particular, I'm ...
0
votes
1answer
24 views

girth of Cayley graphs on abelian groups

I am trying to prove that if $X(G,S) $ is a Cayley graph where $G$ is abelian and $|S|>2$, then $X(G, S)$ contains a $4$-cycle. I found an example proof at the following link: ...
3
votes
2answers
107 views

On the Usual Orientation of Cubic Graphs in Random Construction of Riemann Surfaces

In "Random Construction of Riemann Surfaces", Robert Brooks and Eran Makover say : Definition 2.1 A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on [the cubic graph] $\Gamma$ ...
0
votes
0answers
29 views

Minimize matrix product by changing rows

Consider having a matrix relation like this $$\begin{bmatrix}1&0&0\\-1&1&0\\0&-1&1\\0&0&-1\end{bmatrix}^T\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix} = ...
0
votes
1answer
125 views

Bound on the size of Permutation Set for Isomorphism

This is the second edition of the post. $\textbf{Claim :}$ $G, H $ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \} $ . For each $G_i$ we ...
1
vote
0answers
10 views

How to prove the relation between the directed Laplacian and the number of strongly connected components?

Let be a weighted digraph G (without loops) and its Laplacian L. How to prove that the multiplicity of the zero eigenvalue associated to L is equal the number of strongly connected components of G?
1
vote
2answers
80 views

Example of non-commutative association scheme

I need an example of non-commutative association scheme of ordered 6. I tried to use the example in the book Handbook of Combinatorial Designs, Second Edition by Charles J. Colbourn‏،Jeffrey H. Dini ...