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

learn more… | top users | synonyms

1
vote
1answer
28 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
1answer
12 views

For what functions $f$ is $x^{\sf T}Lf(x) \geq 0$?

Let $L = L^{\sf T} \in \mathbb{R}^{n\times n}$ be a (weighted) Laplacian matrix of a connected undirected graph. For those not familiar with Laplacians (they are positive semidefinite); for simplicity ...
1
vote
1answer
18 views

Surjective homomorphism preserves planarity?

I was just wondering if for surjective homomorphism of G to H, where G is planar hold that H is planar as well. This is clearly false for non-surjective ones, but for surjective? How it is with ...
5
votes
3answers
36 views

Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
0
votes
1answer
54 views

Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
3
votes
1answer
72 views

Does a 2-connected graph, say $G$ have a vertex, say $v$, such that $G-v$ is still 2-connected?

I have been trying to solve this problem for some days. Then, I put the problem here, and it is here for some days. I appreciate it if someone even give me some hint. Assume that $G$ is a 2-...
0
votes
0answers
27 views

how to find the angle of Lovasz umbrella

in the book Thirty-three Miniatures: Mathematical and Algorithmic Applications of in problem 28 The Secret Agent and the Umbrella page 132 (pdf 140) we want to find an orthogonal reperesentation of ...
1
vote
2answers
24 views

Isomorphism of two graphs using adjacency matrix

How can I show that the following two graphs are isomorphic: Steps: The given graphs can be written as:
1
vote
0answers
21 views

Quasi-Group represented by a graph which is not a Triangle-Free Graph locally

Can each of all quasi-groups be represented by a graph (latin square graph), which is not locally triangle free graph ? Quasi Group can be represented by Latin Square matrix, thus by a Latin ...
1
vote
0answers
23 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
17 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
20 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
16 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
95 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
44 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
29 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
61 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
129 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. $K_{...
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
78 views

Can a triangle free graph represent a Group?

Some facts are- Group can be represented by a graph. Group Isomorphism $\leq_p$ Graph Isomorphism. Under this context, my questions is- Can a triangle free graph represent a group? Edit: My ...
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
56 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 $n-1$...
0
votes
1answer
27 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
36 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 $G$...
1
vote
1answer
80 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
65 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
32 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
47 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)$ i.e....
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
42 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
26 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
37 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
199 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
90 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
40 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
56 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
36 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
39 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 - 1\right)}{4}...
11
votes
5answers
597 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 ...
3
votes
1answer
48 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
53 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
25 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 ...