Displaying similar documents to “Spectra of extended double cover graphs”

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 the signless Laplacian spectral characterization of the line graphs of T -shape trees

Guoping Wang, Guangquan Guo, Li Min (2014)

Czechoslovak Mathematical Journal

Similarity:

A graph is determined by its signless Laplacian spectrum if no other non-isomorphic graph has the same signless Laplacian spectrum (simply G is D Q S ). Let T ( a , b , c ) denote the T -shape tree obtained by identifying the end vertices of three paths P a + 2 , P b + 2 and P c + 2 . We prove that its all line graphs ℒ ( T ( a , b , c ) ) except ℒ ( T ( t , t , 2 t + 1 ) ) ( t ≥ 1 ) are D Q S , and determine the graphs which have the same signless Laplacian spectrum as ℒ ( T ( t , t , 2 t + 1 ) ) . Let μ 1 ( G ) be the maximum signless Laplacian eigenvalue of the graph G . We give the limit of μ 1 ( ℒ ( T ( a , b , c ) ) ) , too.

Some graphs determined by their (signless) Laplacian spectra

Muhuo Liu (2012)

Czechoslovak Mathematical Journal

Similarity:

Let W n = K 1 ∨ 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 ≥ 1 , k ≥ 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 ≥ 0 and k ≥ 1 .

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) be a simple graph. A 3 -valued function f V ( G ) → { - 1 , 0 , 1 } is said to be a minus dominating function if for every vertex v ∈ V , f ( N [ v ] ) = ∑ u ∈ N [ v ] f ( u ) ≥ 1 , where N [ v ] is the closed neighborhood of v . The weight of a minus dominating function f on G is f ( V ) = ∑ v ∈ V f ( v ) . The minus domination number of a graph G , denoted by γ - ( G ) , equals the minimum weight of a minus dominating function on G . In this paper, the following two results are obtained. (1) If G is a bipartite graph of order n , then γ - ( G ) ≥ 4 n + 1 - 1 - n . (2) For any negative integer k and any positive integer...

The spectral determinations of the connected multicone graphs K w ▽ m P 17 and K w ▽ m S

Ali Zeydi Abdian, S. Morteza Mirafzal (2018)

Czechoslovak Mathematical Journal

Similarity:

Finding and discovering any class of graphs which are determined by their spectra is always an important and interesting problem in the spectral graph theory. The main aim of this study is to characterize two classes of multicone graphs which are determined by both their adjacency and Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let K w denote a complete graph on w vertices, and let m be a positive integer number. In A. Z. Abdian (2016)...

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 ) ≥ ⎡ n / 3 ⎤ , and provide a characterization of graphs achieving this bound.