2
$\begingroup$

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below:

enter image description here

I want to prove that $0$ is an eigenvalue of the adjacency matrix of $G$.

I think that the adjacency matrix of its line graph has -2 as an eigenvalue, but I don't know this can be helpful or not. furthermore, the number of vertices of $G$ should be even and $|E(G)|=\frac{3|V(G)|}{2}$.

I will be so thankful for your helpful comments and answers.

$\endgroup$
4
  • $\begingroup$ What do you mean Eigenvalue? Are we supposed to build a matrix from the graph? Like the laplacian or something? $\endgroup$
    – Asinomás
    Jan 7, 2015 at 15:44
  • $\begingroup$ maybe this help to relate: en.wikipedia.org/wiki/Incidence_matrix $\endgroup$
    – janmarqz
    Jan 7, 2015 at 15:53
  • $\begingroup$ Given the reference to $-2$ as an eigenvalue of the line graph, the obvious interpretation is the adjacency matrix. $\endgroup$ Jan 7, 2015 at 18:24
  • $\begingroup$ I mean the eigenvalue of adjacency matrix of $G$. I edited my question. $\endgroup$
    – A-213
    Jan 7, 2015 at 19:30

2 Answers 2

3
$\begingroup$

The edges of the Petersen graph can be partitioned into three copies of your given graph, but its eigenvalues are 3, 1, $-2$. So the claim is false.

What is true is that if there is a partition as described then $-2$ is an eigenvalue. This is because if you pass to the line graph, the vertices that correspond to the central edges of your subgraphs form a perfect 1-code and if a regular graph has a perfect 1-code, it has $-1$ as an eigenvalue. This gives an eigenvalue of $-2$ in the original graph.

$\endgroup$
1
  • $\begingroup$ Nice counter example dear Godsil!! Thank you very much. Your answer is very helpful for me. $\endgroup$
    – A-213
    Jan 8, 2015 at 11:44
1
$\begingroup$

for the adjacency matrix of $G$ we can build an eigenvector $X$ where $AX=0$,for any vertex of degree 3,I mean similar to 1 and 2 put 2 and for others put -1,this vector will be the eigenvector of $\lambda=0$.

$\endgroup$
4
  • $\begingroup$ I cannot see how the vector you mentioned can be considered as an eigenvector of $G$ in general. $\endgroup$
    – A-213
    Jan 7, 2015 at 19:34
  • $\begingroup$ If we label each vertex of graph with its corresponding value of the eigenvector, for each vertex, in this case, the summation of labels of all neighbors must be zero. So your vector can not work. $\endgroup$
    – A-213
    Jan 8, 2015 at 11:56
  • $\begingroup$ but once I have checked it!by the way I tried to give an Idea! $\endgroup$
    – kpax
    Jan 8, 2015 at 12:15
  • $\begingroup$ Thanks alot. I understand. $\endgroup$
    – A-213
    Jan 8, 2015 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .