On the signless Laplacian spectral characterization of the line graphs of $T$-shape trees

Guoping Wang; Guangquan Guo; Li Min

Displaying similar documents to “On the signless Laplacian spectral characterization of the line graphs of $T$ -shape trees”

Spectra of extended double cover graphs

Zhibo Chen (2004)

Czechoslovak Mathematical Journal

Similarity:

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph $G$ with vertex set $V = {v_{1}, v_{2}, \dots, v_{n}}$ , the extended double cover of $G$ , denoted $G^{*}$ , is the bipartite graph with bipartition $(X, Y)$ where $X = {x_{1}, x_{2}, \dots, x_{n}}$ and $Y = {y_{1}, y_{2}, \dots, y_{n}}$ , in which $x_{i}$ and $y_{j}$ are adjacent iff $i = j$ or $v_{i}$ and $v_{j}$ are adjacent in $G$ . In this paper we obtain formulas for the characteristic polynomial and the spectrum of $G^{*}$ in terms of the corresponding information of $G$ . Three formulas are derived for the number of spanning trees...

Some graphs determined by their (signless) Laplacian spectra

Muhuo Liu (2012)

Czechoslovak Mathematical Journal

Similarity:

Let $W_{n} = K_{1} \lor C_{n - 1}$ be the wheel graph on $n$ vertices, and let $S (n, c, k)$ be the graph on $n$ vertices obtained by attaching $n - 2 c - 2 k - 1$ pendant edges together with $k$ hanging paths of length two at vertex $v_{0}$ , where $v_{0}$ is the unique common vertex of $c$ triangles. In this paper we show that $S (n, c, k)$ ( $c \geq 1$ , $k \geq 1$ ) and $W_{n}$ are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that $S (n, c, k)$ and its complement graph are determined by their Laplacian spectra, respectively, for $c \geq 0$ and $k \geq 1$ .

Rotation and jump distances between graphs

Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson (1997)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least...

On graphs with the largest Laplacian index

Bo Lian Liu, Zhibo Chen, Muhuo Liu (2008)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$ , namely, the greatest Laplacian eigenvalue of $G$ , is well known to be bounded above by $n$ . In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$ . Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$ -regular graph $G$ of order $n$ with the...

On the Spectral Characterizations of Graphs

Jing Huang, Shuchao Li (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let [...] p2q $𝒰_{p}^{2 q}$ be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ⩽ p) vertices on Cp, whereas [...] p2q $𝒱_{p}^{2 q}$ the subset of [...] p2q $𝒰_{p}^{2 q}$ with odd p...

On integral sum graphs with a saturated vertex

Zhibo Chen (2010)

Czechoslovak Mathematical Journal

Similarity:

As introduced by F. Harary in 1994, a graph $G$ is said to be an $i n t e g r a l$ $s u m$ $g r a p h$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$ , $u v$ is an edge of $G$ if and only if $f (u) + f (v) = f (w)$ for some vertex $w$ in $G$ . We prove that every integral sum graph with a saturated vertex, except the complete graph $K_{3}$ , has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

Displaying similar documents to “On the signless Laplacian spectral characterization of the line graphs of T -shape trees”

Displaying similar documents to “On the signless Laplacian spectral characterization of the line graphs of $T$ -shape trees”