Tagged Questions

1
vote
0answers
32 views

Proof is needed for a lower bound of the maximal eigen-value of a non-negative, irreducible, integer matrix

$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eigen vector ($x$). It ...
2
votes
1answer
52 views

Does the kernel need to be the full automorphism group of the induced subgraph?

Let $\Gamma$ be a simple graph. Suppose its automorphism group $G=\text{Aut}\Gamma$ is imprimitive on its vertex set $V$. Take a block system $\mathcal{B}$ of $V$. Let $B\in\mathcal B$, and let ...
1
vote
1answer
34 views

Godsil & Royle, Theorem 9.5.1: Extension for digraphs?

I was wondering if there is an extension to digraphs for Theorem 9.5.1 in Godsil & Royle's Algebraic Graph Theory. The Theorem can also be found in Willem Haemers paper Interlacing Eigenvalues ...
1
vote
1answer
30 views

Uniqueness of Seifert graphs

If we make the bands and disks of a Seifert surface really small and really thin the surface collapses to a graph. It is called a Seifert graph. If it is not a directed and weighted graph, can we ...
1
vote
0answers
36 views

Bounds on the maximum eigenvalue of the adjacency matrix of a graph.

I managed to proof the following result for the maximum eigenvalue: $ d_{avg}\leq \lambda_{max} \leq \Delta(G) $ where $d_{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum ...
0
votes
1answer
45 views

Counting graphs with even degrees! Trouble with formula!

There is one topic about "Counting graphs with even degrees" here that tell something about edge space, vector space, cut space and ... I have a graph exam tomorrow, and there is a problem that said ...
0
votes
0answers
43 views

How to prove this relation between characteristic polynomials?

The problem wich I need an is idea to find an answer is below: Prove that if the graph $H$ is obtained from the graph $G$ by subdividing the edge $uv$ then ...
3
votes
2answers
43 views

Graphs with zero spectrum / nilpotent symmetric matrices

Is there a graph theoretic characterization of those graphs with zero spectrum? Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...
1
vote
1answer
55 views

Adjacency matrix defines a distance metric

Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that \begin{equation} \sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f} \end{equation} where $\mathbf{f}$ holds values of ...
9
votes
2answers
115 views

Representation theorems for groups

There are two baffling representation theorems for groups: Every group is isomorphic to the automorphism group of some graph. (see Frucht's theorem) Every group is isomorphic to the fundamental ...
0
votes
0answers
42 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
0
votes
1answer
55 views

Example of an even subgraph that can't be decomposed into simple cycles?

In discussion of a lemma in the paper "Minimum cuts and shortest homologous cycles" Chambers Erickson and Nayyeeri make the claim that an even subgraph of an embedded graph can be decomposed into a ...
1
vote
2answers
55 views

Spectrum of a 3-regular graph

Let $D_n$ be the following graph on $2n$ vertices: $V=\mathbb{Z}_n\times\{0,1\}$ and $E=\{(i,j)(i+1,j): i\in \mathbb{Z}_n,j\in \{0,1\}\}\cup\{(i,0)(i,1):i\in\mathbb{Z}_n\}$. What is the spectrum of ...
1
vote
1answer
53 views

Spectrum of the cycle graph $C_n$

I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by ...
4
votes
1answer
119 views

What is the difference between first and second right eigenvectors of a row stochastic matrix and their meaning?

In an $n\times n$ non negative row stochastic matrix (rows sum up to 1). The entries of the stochastic matrix I have represent directed links between countries. Why is the first right eigenvector a ...
1
vote
2answers
113 views

A property of incidence matrix of a graph

Let $G$ be an oriented graph with incidence matrix $Q$, and let $B:=[b_{ij}]$ be a $k\times k$ sub-matrix of $Q$ which is non-singular. Can there exist two distinct permutations $\sigma$ and ...
0
votes
1answer
118 views

Prove that the group of automorphisms of a labelled Cayley graph of a group G is the group G itself (Just stumped on one direction)

I feel like for this question it is just a matter of showing the mapping in both directions, from the group to the graph and the graph to the group. So for the mapping from the group to the graph, I ...
2
votes
0answers
99 views

The dodecahedral graph is not a Cayley graph

Consider the following question Is the dodecahedral graph $D$ a Cayley graph? I would like to show that it is not and I am lazy hence I am looking for the most cheap way. I see two approaches ...
3
votes
0answers
76 views

Edge-connectivity of edge-transitive graphs

If $G$ is a vertex-transitive graph then it is well known that the edge connectivity of $G$, $\kappa'(G)$ equals to $\rm{val}(G)$ - the degree of a vertex in $G$ (note that $G$ is regular.) My ...
0
votes
1answer
58 views

Blocks of imprimitivity in vertex-transitive graphs

An exercise from a book that I am currently studying asks to show the following. Let $B$ be a block of imprimitivity of $\rm{Aut}(G)$ for a vertex-transitive graph $G.$ Then the graph induced by ...
1
vote
1answer
148 views

Generating non-isomorphic graph by adding two edges to a fixed graph

I am given a graph $G$ a fixed vertex $v \in V(G)$ and sets $S_1,S_2 \subseteq V(G).$ The problem I am currently studying requires to answer the following question Compute all non-isomorphic ...
6
votes
1answer
93 views

Proving that the characteristic polynomial of a bipartite graph has alternating positive and negative coefficients

It is well known that the characteristic polynomial of a bipartite graph is of the form $\sum_{k=0}^n (-1)^kc_{2k} x^{2k}$ where $c_{2k} \geq 0$. I can prove why there cannot be any odd powered ...
4
votes
2answers
115 views

Graphs whose automorphism group is the cyclic group

I would like a good hint for the following problem that takes into account the position at which I am stuck. The problem is as follows Let $\mathbb{Z}_n$ be the cyclic group of order $n.$ Find a ...
4
votes
1answer
48 views

A group and an associated digraph

I am trying to understand the proof of the following statement: Let $\Gamma=\{g_1,\cdots,g_n\}$ be a group. Define a digraph $G$ by joining $g_i$ to $g_j$ by an edge of color $k$ if ...
5
votes
1answer
147 views

Almost all labeled graphs implies almost all graphs?

I would be thankful if someone could verify the following reasoning. Let $I$ be some graph property that is invariant (chromatic number, connectedness,etc.). Let $p(n)$ be the number of (labeled) ...
4
votes
1answer
103 views

Cayley graphs on small Dihedral and Cyclic group

Consider the following problem Let $n \leq 5$ and let $\Gamma = \mathrm{Cay}(C_{2n},S)$ be the Cayley graph with Cayley set $S$. Show that $\Gamma$ is isomorphic to $\mathrm{Cay}(D_{2n},S')$ ...
2
votes
3answers
75 views

Showing that a specific regular graph has a trivial automorphism group

Consider the graph $G$ in the following picture It can be verified (using Sage or an equivalent program) that $G$ has a trivial automorphism. What I am wondering is how to show this fact by a formal ...
2
votes
1answer
104 views

Graph Laplacian, requirements

What are the necessary and sufficient conditions for a PSD matrix $S$, to be a graph Laplacian? I know $S1=0$ is required. But clearly a real zero sum PSD matrix is not necessarily a graph Laplacian. ...
0
votes
1answer
168 views

Explanation of Unweighted Shortest path definition from Introduction to Algorithms by Cormen et al

From Introduction to Algorithms by Cormen et al: We are given a directed graph G = (V,E) and vertices ${u,v}\in V $ and then the define Unweighted shortest path to ...
0
votes
1answer
321 views

What is a subproblem graph in dynamic programming parlance?

I know what dynamic programming is but I do not really understand the concept of subproblem graph for a dynamic programming ? How are they useful ? When solving problem by dynamic programming should ...
1
vote
2answers
413 views

What is the definition of an weighted graph?

In graph theory which one of these two will be called a weighted graph ? A graph where vertices have some weights or vales . A graph where edges have some weights or values . A graph where both ...
4
votes
1answer
101 views

characteristic polynomial of the adjacency matrix of a tree

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$ where $N_k(T)$ is the number ...
4
votes
1answer
183 views

Graphs with a unique $3$-path free acyclic orientation up to isomorphism.

Let $\Gamma$ be a simple, $3$-colorable graph such that, up to isomorphism, there exists exactly one acyclic orientation of $\Gamma$ that does not contain a directed 3-path. (To be clear, when I say ...
1
vote
1answer
250 views

How to prove that a matrix is positive definite?

Let $L$ be a Laplacian matrix of a strong connected and balanced directed graph. Define $$ L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$ Let $D$ be a diagonal matrix with $$ D=\begin{bmatrix} d_{1} & ...
2
votes
0answers
39 views

Properties of a generalized graph

I'll start with formulating my problem and then ask my question: To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
5
votes
1answer
713 views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
1
vote
0answers
63 views

algebraic connectivity of the giant component

In percolation theory there is this idea of a giant component, and I am curious what is known about its algebraic connectivity. I looked on google but I was not able to find anything particularly ...
4
votes
0answers
155 views

“Semidirect product” of graphs?

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd ...
4
votes
2answers
172 views

Graphs with eigenvalues of large multiplicity

For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ...