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

learn more… | top users | synonyms

1
vote
0answers
20 views

Number of Vertices with $\mu$ Common Neighbor

$\mathcal{G}$ is a graph class. Each graph $G$ of $\mathcal{G}$ has the following properties- $G$ is a $k$ (variable with respect to different graphs) regular graph of $n$ vertices. The vertex set ...
0
votes
1answer
14 views

How can we show Aut(J(v,k,i)) contains a subgroup isomorphic to sym(v), where v>k>i .

This is Lemma 1.6.2 from the Book Algebraic Graph Theory by Chris Godsil and Gordon Royle. I tried proving this but not able to come up with a good proof, can some one please help me in doing this.
1
vote
0answers
16 views

A retract H of G is an induced subgraph of G. show that it is isometric.

Let G and H be graphs. A homomorphism φ : G → H is a map φ : V(G) → V(H) which preserves edges, that is, {x, y} ∈ E(G) ⇒ {φ(x), φ(y)} ∈ E(H). We write G → H if there is a homomorphism φ : G → H. Let ...
2
votes
1answer
13 views

show that if two trees have isomorphic line graphs , they are isomorphic.

i want to use Whitney isomorphism theorem : if the line graphs of two connected graphs are isomorphic , then the underlying graphs are isomorphic. except in the case of the triangle graph K3 and K1,3 ...
2
votes
2answers
87 views

Automorphism group of a graph = Automorphism group of that graph's adjacency matrix?

Is automorphism group (or set) of a graph $G$ equal to the automorphism group (or set) of adjacency matrix of $G$? Example: $G_1, G_2$ are separate graphs where $G_1^{\pi}= G_2$ and $ G= \bar ...
4
votes
1answer
39 views

How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem- Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time ...
0
votes
0answers
24 views

How to find the size of the largest connected component of a graph from the adjacency matrix, without using BFS/DFS?

Is there a known way to compute the size of the largest connected component of an undirected graph using just the matrix operations on the adjacency matrix or the laplacian matrix of the graph?
1
vote
1answer
59 views

How to represent tripartite graphs algebraically (as matrices)?

A bipartite graph can be represented by an adjacency matrix, or specifically, by a biadjacency matrix. Formally, let $G = (U, V, E)$ be a bipartite graph with parts $U = \{u_1, \ldots, u_r\}$ and $V ...
3
votes
1answer
117 views

Eigenvalues of “almost” complete bipartite graph ?!

Please note that I'm just looking for a partial answer to this question. Definition Let $G=U\cup V$ be a bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. ...
2
votes
1answer
28 views

Existence of a $d$-regular graph such that $|N_G(x) \cap N_G(y)| = \lambda$.

Consider a $d$-regular graph $G = (V, E)$ of order $n$ such that $|N_G(x) \cap N_G(y)| = \lambda$ for all distinct $x, y \in V$. By double counting we have a necessary condition $\lambda (n - 1) = d(d ...
0
votes
1answer
71 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
18 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
55 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
24 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
33 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
78 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
17 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
62 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
27 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
31 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
43 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
23 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
33 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
35 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
198 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
109 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
87 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
38 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
50 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
38 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
590 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
54 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 ...
2
votes
1answer
45 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
49 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
23 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
125 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
68 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
26 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
32 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
12 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
104 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
159 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$. ...