-2
votes
0answers
7 views

Graph Theory - Lower bounds

I am trying to solve for the following problem: Find (and justify) a lower bound for 0(G) in terms of X'(G) and E|(G)| and alpha'(G). (where alpha'(G) represents the maximum size of a matching in ...
0
votes
0answers
17 views

Number of edges of a plane graph isomorphic to its dual

I am having trouble proving the following statement: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges.
1
vote
1answer
41 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 ...
1
vote
1answer
24 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
56 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
66 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
22 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
21 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
52 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
74 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
40 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
43 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
32 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
64 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
32 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
49 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
34 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
33 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
216 views

Chromatic polynomial of a grid graph

I have the following graph with $nm$ vertices: ...
1
vote
1answer
56 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
73 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: ...
13
votes
3answers
231 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
48 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
42 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
69 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
85 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
53 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
121 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
93 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
96 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
23 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
73 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
48 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
37 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
113 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
126 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, ...
0
votes
1answer
77 views

how to prove a result

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
0
votes
2answers
79 views

non-Hamiltonian Cycles: How to Prove for Small Graphs

How do I prove that the following graph is a non-Hamiltonian cycle? $\hspace{5.3cm}$ I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. ...
2
votes
1answer
92 views

associativity in graph theory

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking ...
0
votes
0answers
35 views

How to choose the adjacency set

Given a group $G$ of order a composite number, how should one construct the adjacency set $S$ such that the underlying Cayley graph $\Gamma=\text{Cay}(G,S)$ admits a block system under ...
0
votes
1answer
153 views

length of a walk in product graph

I was doing tensor product of graphs. We know that to find a walk between every two vertices x and y of any arbitrary length l in G, the graph must contain an odd cycle. I am stuck here. Is it ...
2
votes
1answer
68 views

new definition in graphs

I was reading a topic on wikipedia. There a product "corona product" was defined as : Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and ...
3
votes
2answers
80 views

a basic doubt about definition in graph theory

Friends, I have a very basic doubt about neighborhood of a vertex. I was going through some pdf and their it was written about i-th neighbor of v, $v \in V(G)$. Can anybody explain me the term i-th ...
0
votes
1answer
89 views

clearing doubt over a definition

Can anybody tell me what is a Zig-Zag product in graph theory? I am getting no idea how this product is done and how edges are defined in the product? I have some links: ...
-1
votes
1answer
70 views

Recurrence Relation Over Paths [closed]

Let $v$ and $w$ be distinct vertices in $K_n$. Let $p_m$ denote the number of paths of length $m$ from $v$ to $w$ in $K_n$, $1\leq m \leq n$. $(a)$ $\hspace{1cm}$Derive a recurrence relation for ...
1
vote
2answers
501 views

Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question: How many antisymmetric relations are there on an $n$-element set? Guess: I suspect that there are $2^n$ such relations. Discussion: I'm told that anti-symmetric relations on a ...
3
votes
1answer
77 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...