What is the spectrum of graphs having a vertex of full degree? A vertex v is said to be full degree vertex if deg(v)=n-1, where n is the number of vertices in G.
Hello!
If a graph G has a full degree vertex, then G would be a star, Sn, and its spectrum is ± sqrt(n-1), 0. The multiplicity of 0 is n-2.
In the case where G is isomorphic to Kn, the complete graph on n vertices, its spectrum is n-1, (- 1). The multiplicity of (-1) is n-1.
On the other hand, if a graph G has a full degree vertex, then the greater Laplacian eigenvalue of G satisfies the following.
Lemma
Let G be a connected graph of order n, then λ₁(L (G)) ≥ Δ + 1.
Equality is achieved if and only if Δ = n-1. where Δ denotes the highest degree vertex.
This result is in the following paper:
R. Grone, R. Merris. The Laplacian spectrum of a graph II. SIAM J. Discr.
Math. 7 (1994) 221--229.
Best regards
Jonnathan
Complete graph Kn has full vertex degree. Its spectrum consists of n-1and -1 (n-1times).
Dear Jonnathan Rodríguez, Dr. Ramane sir,
Thank you very much for your answer. I know the spectrum of the complete graph and star graph. In general, if G has a full vertex degree I have observed the following:
1. Spectral radius is nearly equal to $\Delta(G)$
2. Some times all eigenvalues are integers. Therefore, G may be integral graph.
3. If G is not star graph and having full vertex degree then G is non-bipartite graph. Therefore, spectrum of non-bipartite graph may help to characterize these graphs.
In general can we write a theorem for general graphs having full degree vertex?
Dr Sunil Kumar M Hosamani
Along with greet him, I think we can write a theorem concerning graphs with full degree vertex.
For my part, any progress will let you know.
We are in contact.
Best regards
Jonnathan
Actually I was expecting something different answer. I am sorry I couldn't able to greet both of you. Sure we will work on this topic. If I do any progress I will mail you.
Regards
Sunilkumar Hosamani
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs