pith. sign in

arxiv: 1310.1003 · v1 · pith:2IYP6ZO6new · submitted 2013-10-03 · 🧮 math.CO

The signature of line graphs and power trees

classification 🧮 math.CO
keywords graphindexinertiasignaturetreesconjecturecyclesgraphs
0
0 comments X
read the original abstract

Let $G$ be a graph and let $A(G)$ be the adjacency matrix of $G$. The signature $s(G)$ of $G$ is the difference between the positive inertia index and the negative inertia index of $A(G)$. Ma et al. [Positive and negative inertia index of a graph, Linear Algebra and its Applications 438(2013)331-341] conjectured that $-c_3(G)\leq s(G)\leq c_5(G),$ where $c_3(G)$ and $c_5(G)$ respectively denote the number of cycles in $G$ which have length $4k+3$ and $4k+5$ for some integers $k \ge 0$, and proved the conjecture holds for trees, unicyclic or bicyclic graphs. It is known that $s(G)=0$ if $G$ is bipartite, and the signature is closely related to the odd cycles or nonbipartiteness of a graph from the existed results. In this paper we show that the conjecture holds for the line graph and power trees.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.