1
vote
1answer
40 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
48 views

what is the significance of the inverse of an adjacency matrix?

Suppose I have a graph and I calculate the eigenvalues of the adjacency matrix and find that there are some number of zero eigenvalues. Do zero eigenvalues have any significance? Also is there a good ...
0
votes
1answer
26 views

Constructing an eigenvector for a certain matrix representing a graph with a perfect code

Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$ By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A ...
0
votes
0answers
11 views

compare magnitude of elements of Perron-Frobenious vector

Consider a nonnegative, primitive matrix $A=(a_{ij})_{n\times n}$ with positive diagonals. From the Perron-Frobenious theorem, the spectral radius $\rho(A)$ is an eigenvalue of $A$ and we have a ...
0
votes
1answer
60 views

Example of non-Abelianness of symmetric group for graphs

I know that for $n \ge 3$, $S_n$ is non-Abelian. I would like to work out an example in terms of graphs so to make it sure that I understand it right. A symmetric group of graphs of four vertices, ...
3
votes
0answers
40 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
2
votes
1answer
41 views

Automorphisms groups of direct product of graphs

Direct product of graphs $G$ and $H$ is a graph $G\times H$ for which $V(G\times H)=V(G)\times V(H)$ $E(G\times H)=\left\{(g_1,h_1)(g_2,h_2):\ g_1g_2\in E(G),\ h_1h_2\in E(H)\right\}$. Direct ...
0
votes
0answers
56 views

number of symmetries of an arbitrary graph

Given an (undirected) graph G, is there way to (approximately) estimate the order of Aut(G)-- i.e., the number of permutations ...
1
vote
0answers
32 views

Spectrum of an infinite graph independent of labelling

Does there exist an infinite graph whose spectrum does not depend upon the labelling of the graph? While evaluating the spectrum, I am considering adjacency matrix of the infinite graph as a bounded ...
2
votes
1answer
65 views

Eigenvalues of the distance-k graph of a graph

Let $G$ be a (finite, simple, connected) graph. Define the distance-$k$ graph $G_k$ to be the graph with the same vertex set and $x\sim y$ iff $d(x,y)=k$. A graph is integral if all of the eigenvalues ...
0
votes
0answers
85 views

Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = '$k-1$' for $k =1,2,\ldots. n $

There is a transitive tournament (T) with $n > 1$ vertices and the score sequence is defined as $s_1, s_2, \ldots,s_n$ Prove that T is transitive if and only if the score of the $k^{th}$ vertex ...
2
votes
1answer
41 views

Graphs that are vertex transitive but not edge transitive

A graph $G$ is vertex transitive if for any two vertices $x$ and $y$ of $G$ there is an automorphism of $G$ that sends $x$ to $y$. Similarly, $G$ is edge transitive if for any two edges $e$ and $f$ of ...
1
vote
1answer
81 views

Is there a cayley graph for the Klein bottle?

When studying algebraic topology we learned about the fundamental group of the $2$-torus $T^2$ which is isomorphic to $$\langle a, b \mid aba^{-1}b^{-1} \rangle$$ (the free abelian group on two ...
1
vote
2answers
75 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
2
votes
1answer
36 views

Existence of a (19, 6, 1, 2) strongly regular graph

While reading Is there a graph with 99 vertices... I became curious about smaller graphs satisfying the property. According to Wikipedia, strongly regular graphs must satisfy the relation: ...
2
votes
1answer
65 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
3
votes
2answers
76 views

Is the eigenvectors of vertex transitive graphs bounded

For a connected and regular graph $G$ with degree $ d $ at each vertex and adjacency matrix $A$, the normalized Laplacian of $G$ is defined as $L = I-\frac{1}{d}M$. Let $\psi$ be an eigenvector of $L$ ...
1
vote
0answers
44 views

Automorphism group of a bipartite regular graph

Showing an automorphism group of complete bipartite graph $K_{n,m}$ is easy. I'm wondering if there is an classification of automorphism groups of bipartite regular graphs. Did anyone heard something ...
1
vote
0answers
23 views

automorphisms of the infinite trivalent tree

Let $T$ be the infinite trivalent tree. I want to show that if $\alpha,\beta,\alpha',\beta'$ are vertices of the tree such that the distances $d(\alpha,\beta)$ and $d(\alpha',\beta')$ are equal, then ...
0
votes
1answer
56 views

Find eigenvalues from a given relation.

This is a simple problem of linear algebra. One without knowing graph theory may solve it. I am missing a small easy logic. Description: Let $G$ be a graph with $n$ vertices and $G^c$ is its ...
1
vote
1answer
77 views

The properties of graph and its relation with the largest eigenvalue

When I was solving questions from a graph theory book by Bondy and Murty, I came across this problem: ( Note: $\Delta$ represents the maximum degree. ) Show that: a) no eigenvalue of a graph ...
0
votes
1answer
45 views

Explicit expression of eigenvalue and eigenvector of a graph

Could any one tell me what kind of graph has the explicit expression of its eigenvalue and eigenvector? Thanks!
1
vote
0answers
44 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem 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
2answers
40 views

Chromatic Polynomial for a Graph

I have The chromatic polynomial for this is given as $P(G_e,\lambda)=\lambda(\lambda-1)^3$. How is this calculated?
3
votes
0answers
98 views

Chromatic Number and Chromatic Polynomial of a Graph

I'm studying chromatic numbers and chromatic polynomials of graphs at the moment and I know the subtle connection between the two: Let $G$ be a graph, $\chi(G)$ be it's chromatic number and $p_G(x)$ ...
1
vote
0answers
39 views

Eigenvalue gap of a graph

How to compute the eigenvalue gap of a graph. For example how does it work for the star graph? Let us assume that every node has a self-loop. Since this should make the eigenvalues positive, I would ...
0
votes
0answers
55 views

Quotient group and graphs

what is the Quotient group and how we can compute it for Petersen graph? what properties of graphs are incurred in the quotient groups of graphs? for example suppose G=(V,E) , D is the free abelian ...
2
votes
1answer
47 views

A question about the interlacing of symmetric matrices (graph interlacing)

Reading the paper of Haemers on graph interlacing I came across the following question. Let $A$ be a real symmetric matrix partitioned into $m \times m$ blocks and suppose $B$ is a $m \times m$ ...
1
vote
0answers
54 views

clique number of generalized Johnson graph $J(4n-1,2n-1,n-1)$

The generalized Johnson graph $J(v,k,r)$ is defined to be the graph whose vertex set is the set of all $k$-element subsets of $\{1,2,\ldots,v\}$, and with two vertices adjacent iff their intersection ...
1
vote
2answers
306 views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
1
vote
1answer
83 views

what is the maximum number of faces with n vertex in planar graphs?

what is the maximum number of faces with n vertex in planar graphs? v=number of vertices f= number of faces for example if v=3 -> max(f)=2 v=4 -> max(f)=4 (a triangle with a point in inner face of ...
2
votes
1answer
84 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
14
votes
3answers
284 views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
0
votes
2answers
51 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
2
votes
0answers
45 views

Adajcency matrix of Kneser Graph

What is the structure of adjacency matrix of Kneser graphs $K(n,k)$? Do they have any nice structure?
3
votes
0answers
81 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
1
vote
0answers
47 views

Isomorphisms from $K_5$ to points in $\mathbb R^4$

Is there an isomorphism from the complete graph $K_5$ to a triangular solid in $\mathbb R^4$? For example $K_3$ is trivially mapped to a triangle, $K_4$ may be mapped to a tetrahedron, so what about ...
4
votes
1answer
95 views

Determining the automorphism group of a disconnected graph

There is this know formula for determining the automorphism group of a graph $G$: let the connected components of $G$ consist of $n_1$ copies of $G_1$, $\dots$, $n_r$ copies of $G_r$, where $G_1, ...
0
votes
1answer
60 views

What is a cycle hypergraph?

What is a cycle hypergraph? Could someone give me good reference or illustrate with a few examples?
1
vote
1answer
135 views

How to express this in matrix notation (row-wise normalisation)

My questions are: How do I describe the row sum of a matrix? How do I describe the number of non-zero elements per row of a matrix in matrix notation? How do I divide a vector elementwise? To give ...
2
votes
0answers
100 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
1
vote
1answer
107 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
0answers
25 views

What is the formal name for my “line & node fixation problem”?

Background: Imagine I have 5 sticks in such a manner that $head_{1}$ is free, $tail_{1}$ connected to $head_{2}$, $tail_{2}$ to $head_{3}$, $tail_{3}$ to $head_{4}$, $tail_{4}$ to $head_{5}$, and ...
3
votes
0answers
74 views

Euler, Grinberg,… who's next?

Given a cubic planar hamiltonian graph with $F$ faces. Let $a_k$ be the number of face of degree $k$ inside and $b_k$ outside the Hamilton cycle. We have the following: $\sum \limits_k ...
0
votes
0answers
49 views

a doubt over a term in paper of graph theory

I was reading a paper http://www.sciencedirect.com/science/article/pii/S0166218X08001960. On the page 38, under the topic The vertex hierarchy I have doubt. From where did the following term come? ...
1
vote
0answers
85 views

A question on graphs

Do there exist a family of graphs with $\Omega(N_{G}^{c})$ edges for some fixed $c > 0$ with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes ...
2
votes
2answers
61 views

a doubt in finding distance in graph theory

I was studying about a product graph which is defined as : . I am taking $G_1$ and $G_2$ as connected graphs. I found that for any 2 vertices $(g,h),(g',g')$, $d(g,h),(g',h')$ = 1 if $g \sim g'$ ...
0
votes
0answers
38 views

simplifying an equation [duplicate]

I gave details here of my last question...I hope this helps I am having doubt over an equation. That is my calculation. Can anybody check and find the error, if any. Specially in the last line. I am ...
1
vote
1answer
114 views

doubt over an equation

I am having doubt over an equation. That is my calculation. Can anybody check and find the error, if any. Specially in the last line. I am confused. Thanks a lot. NOTE : please check only last two ...
3
votes
2answers
129 views

to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, ...