Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the smallest eigenvalues of the line graphs of some trees
188
0
0.0
(
0
)
Added by
Yoshio Sano Ph.D.
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study the characteristic polynomials of the line graphs of generalized Bethe trees. We give an infinite family of such graphs sharing the same smallest eigenvalue. Our family generalizes the family of coronas of complete graphs discovered by Cvetkovic and Stevanovic.
rate research
Read More
A theory of orientation on gain graphs (voltage graphs) is developed to generalize the notion of orientation on graphs and signed graphs. Using this orientation scheme, the line graph of a gain graph is studied. For a particular family of gain graphs with complex units, matrix properties are established. As with graphs and signed graphs, there is a relationship between the incidence matrix of a complex unit gain graph and the adjacency matrix of the line graph.
In this paper, we give a combinatorial characterization of the special graphs of fat Hoffman graphs containing $mathfrak{K}_{1,2}$ with smallest eigenvalue greater than -3, where $mathfrak{K}_{1,2}$ is the Hoffman graph having one slim vertex and two fat vertices.
A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we prove that for every fixed integer $kge 1$, there are only finitely many $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs. To prove the results we use a known structure theorem for ($P_5$,gem)-free graphs combined with properties of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs for $k in {4,5}$ using a computer generation algorithm.
Let $G$ be a graph. For a subset $X$ of $V(G)$, the switching $sigma$ of $G$ is the signed graph $G^{sigma}$ obtained from $G$ by reversing the signs of all edges between $X$ and $V(G)setminus X$. Let $A(G^{sigma})$ be the adjacency matrix of $G^{sigma}$. An eigenvalue of $A(G^{sigma})$ is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let $S_{n,k}$ be the graph obtained from the complete graph $K_{n-r}$ by attaching $r$ pendent edges at some vertex of $K_{n-r}$. In this paper we prove that there exists a switching $sigma$ such that all eigenvalues of $G^{sigma}$ are main when $G$ is a complete multipartite graph, or $G$ is a harmonic tree, or $G$ is $S_{n,k}$. These results partly confirm a conjecture of Akbari et al.
In this paper, we show that all fat Hoffman graphs with smallest eigenvalue at least -1-tau, where tau is the golden ratio, can be described by a finite set of fat (-1-tau)-irreducible Hoffman graphs. In the terminology of Woo and Neumaier, we mean that every fat Hoffman graph with smallest eigenvalue at least -1-tau is an H-line graph, where H is the set of isomorphism classes of maximal fat (-1-tau)-irreducible Hoffman graphs. It turns out that there are 37 fat (-1-tau)-irreducible Hoffman graphs, up to isomorphism.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
