32 results on '"Das, Kinkar Ch."'
Search Results
2. On the second largest normalized Laplacian eigenvalue of graphs.
- Author
-
Sun, Shaowei and Das, Kinkar Ch.
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *BIPARTITE graphs , *MATHEMATICAL bounds , *MATHEMATICAL analysis - Abstract
Abstract Let G = (V , E) be a simple graph of order n with normalized Laplacian eigenvalues ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0. The normalized Laplacian spread of graph G , denoted by ρ 1 − ρ n − 1 , is the difference between the largest and the second smallest normalized Laplacian eigenvalues of graph G. In this paper, we obtain the first four smallest values on ρ 2 of graphs. Moreover, we give a lower bound on ρ 2 of connected bipartite graph G except the complete bipartite graph and characterize graphs for which the bound is attained. Finally, we present some bounds on the normalized Laplacian spread of graphs and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
3. On Laplacian energy, Laplacian-energy-like invariant and Kirchhoff index of graphs.
- Author
-
Das, Kinkar Ch. and Gutman, Ivan
- Subjects
- *
LAPLACIAN matrices , *INVARIANTS (Mathematics) , *KIRCHHOFF'S theory of diffraction , *GROUP theory , *LIE algebras - Abstract
Let G be a connected graph of order n and size m with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 . The Kirchhoff index of G , denoted by Kf , is defined as: K f = n ∑ i = 1 n − 1 1 μ i . The Laplacian-energy-like invariant ( L E L ) and the Laplacian energy ( L E ) of the graph G , are defined as: L E L = ∑ i = 1 n − 1 μ i and L E = ∑ i = 1 n | μ i − 2 m n | , respectively. We obtain two relations on LEL with Kf , and LE with Kf . For two classes of graphs, we prove that L E L > K f . Finally, we present an upper bound on the ratio L E / L E L and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
4. On (distance) Laplacian energy and (distance) signless Laplacian energy of graphs.
- Author
-
Das, Kinkar Ch., Aouchiche, Mustapha, and Hansen, Pierre
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *EIGENVALUES , *MATRICES (Mathematics) , *BOND graphs - Abstract
Let G be a graph of order n . The energy E ( G ) of a simple graph G is the sum of absolute values of the eigenvalues of its adjacency matrix. The Laplacian energy, the signless Laplacian energy and the distance energy of graph G are denoted by L E ( G ) , S L E ( G ) and D E ( G ) , respectively. In this paper we introduce a distance Laplacian energy D L E and distance signless Laplacian energy D S L E of a connected graph. We present Nordhaus–Gaddum type bounds on Laplacian energy L E ( G ) and signless Laplacian energy S L E ( G ) in terms of order n of graph G and characterize graphs for which these bounds are best possible. The complete graph and the star give the smallest distance signless Laplacian energy D S L E among all the graphs and trees of order n , respectively. We give lower bounds on distance Laplacian energy D L E in terms of n for graphs and trees, and characterize the extremal graphs. Also we obtain some relations between D E , D S L E and D L E of graph G . Moreover, we give several open problems in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
5. Proof of conjecture involving algebraic connectivity and average degree of graphs.
- Author
-
Das, Kinkar Ch.
- Subjects
- *
GRAPH connectivity , *LOGICAL prediction , *LAPLACIAN matrices , *EIGENVALUES , *GEOMETRIC vertices - Abstract
Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
6. On Two Conjectures of Spectral Graph Theory.
- Author
-
Das, Kinkar Ch. and Liu, Muhuo
- Subjects
- *
GRAPH theory , *GEOMETRIC vertices , *LAPLACIAN matrices , *EIGENVALUES , *SPECTRAL geometry - Abstract
Let G=(V,E)
be a simple graph. Denote by D (G ) the diagonal matrix of its vertex degrees and byA (G ) its adjacency matrix. Then the Laplacian matrix and the signless Laplacian matrix ofG are L(G)=D(G)-A(G)and Q(G)=D(G)+A(G) , respectively. Also denote by λ1(G) , a (G ), q1(G)and δ(G) the largest eigenvalue of A (G ), the second smallest eigenvalue ofL (G ), the largest eigenvalue ofQ (G ) and the minimum degree ofG , respectively. In this paper, we give partial proofs to the following two conjectures: (i)Aouchiche (Comparaison Automatisée d’Invariants en Théorie des Graphes,2006 ) ifG is a connected graph, then a(G)/δ(G)is minimum for graph composed of 2 triangles linked with a path. (ii)Aouchiche et al. (Linear Algebra Appl 432:2293-2322, 2010 ) and Cvetković et al. (Publ Inst Math Beogr 81(95):11-27,2007 ) ifG is a connected graph with n≥4vertices, then q1(G)-2λ1(G)≤n-2n-1 with equality holding if and only if G≅K1,n-1 . [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
7. Distance between the normalized Laplacian spectra of two graphs.
- Author
-
Das, Kinkar Ch. and Sun, Shaowei
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *EIGENVALUE equations , *ISOMORPHISM (Mathematics) , *GEOMETRIC vertices - Abstract
Let G = ( V , E ) be a simple graph of order n . The normalized Laplacian eigenvalues of graph G are denoted by ρ 1 ( G ) ≥ ρ 2 ( G ) ≥ ⋯ ≥ ρ n − 1 ( G ) ≥ ρ n ( G ) = 0 . Also let G and G ′ be two nonisomorphic graphs on n vertices. Define the distance between the normalized Laplacian spectra of G and G ′ as σ N ( G , G ′ ) = ∑ i = 1 n | ρ i ( G ) − ρ i ( G ′ ) | p , p ≥ 1 . Define the cospectrality of G by c s N ( G ) = min { σ N ( G , G ′ ) : G ′ not isomorphic to G } . Let c s n N = max { c s N ( G ) : G a graph on n vertices } . In this paper, we give an upper bound on c s N ( G ) in terms of the graph parameters. Moreover, we obtain an exact value of c s n N . An upper bound on the distance between the normalized Laplacian spectra of two graphs has been presented in terms of Randić energy. As an application, we determine the class of graphs, which are lying closer to the complete bipartite graph than to the complete graph regarding the distance of normalized Laplacian spectra. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
8. The (signless) Laplacian spectral radii of c -cyclic graphs with n vertices, girth g and k pendant vertices.
- Author
-
Liu, Muhuo, Das, Kinkar Ch., and Lai, Hong-Jian
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *GRAPH connectivity , *GEOMETRIC vertices , *EXTREMAL problems (Mathematics) - Abstract
Letdenote the class ofc-cyclic graphs withnvertices, girthandpendant vertices. In this paper, we determine the unique extremal graph with largest signless Laplacian spectral radius and Laplacian spectral radius in the class of connectedc-cyclic graphs withvertices, girthgand at mostpendant vertices, respectively, and the unique extremal graph with largest signless Laplacian spectral radius ofwhenand, and we also identify the unique extremal graph with largest Laplacian spectral radius inin the caseand eitherandgis even orandgis odd. Our results extends the corresponding results of [Sci. Sin. Math. 2010;40:1017–1024, Electron. J. Combin. 2011; 18:p.183, Comput. Math. Appl. 2010;59:376–381, Electron. J. Linear Algebra. 2011;22:378–388 and J. Math. Res. Appl. 2014;34:379–391]. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
9. Kite graphs determined by their spectra.
- Author
-
Das, Kinkar Ch. and Liu, Muhuo
- Subjects
- *
GRAPH theory , *SPECTRUM analysis , *GEOMETRIC vertices , *LAPLACIAN matrices , *APPLIED mathematics - Abstract
A kite graph Ki n , ω is a graph obtained from a clique K ω and a path P n − ω by adding an edge between a vertex from the clique and an endpoint from the path. In this note, we prove that K i n , n − 1 is determined by its signless Laplacian spectrum when n ≠ 5 and n ≥ 4, and K i n , n − 1 is also determined by its distance spectrum when n ≥ 4. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
10. Maximum Laplacian energy of unicyclic graphs.
- Author
-
Das, Kinkar Ch., Fritscher, Eliseu, Pinheiro, Lucélia Kowalski, and Trevisan, Vilmar
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *MATHEMATICAL bounds , *GRAPH connectivity , *GEOMETRIC vertices , *EIGENVALUES - Abstract
We study the Laplacian and the signless Laplacian energy of connected unicyclic graphs, obtaining a tight upper bound for this class of graphs. We also find the connected unicyclic graph on n vertices having largest (signless) Laplacian energy for 3 ≤ n ≤ 13 . For n ≥ 11 , we conjecture that the graph consisting of a triangle together with n − 3 balanced distributed pendent vertices is the candidate having the maximum (signless) Laplacian energy among connected unicyclic graphs on n vertices. We prove this conjecture for many classes of graphs, depending on σ , the number of (signless) Laplacian eigenvalues bigger than or equal to 2. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
11. Relations between degrees, conjugate degrees and graph energies.
- Author
-
Das, Kinkar Ch., Mojallal, Seyed Ahmad, and Gutman, Ivan
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *MATHEMATICAL bounds , *MATHEMATICAL sequences , *MATHEMATICAL proofs - Abstract
Let G be a simple graph of order n with maximum degree Δ and minimum degree δ . Let ( d ) = ( d 1 , d 2 , … , d n ) and ( d ⁎ ) = ( d 1 ⁎ , d 2 ⁎ , … , d n ⁎ ) be the sequences of degrees and conjugate degrees of G . We define π = ∑ i = 1 n d i and π ⁎ = ∑ i = 1 n d i ⁎ , and prove that π ⁎ ≤ L E L ≤ I E ≤ π where LEL and IE are, respectively, the Laplacian-energy-like invariant and the incidence energy of G . Moreover, we prove that π − π ⁎ > ( δ / 2 ) ( n − Δ ) for a certain class of graphs. Finally, we compare the energy of G and π , and present an upper bound for the Laplacian energy in terms of degree sequence. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
12. Distribution of Laplacian eigenvalues of graphs.
- Author
-
Das, Kinkar Ch., Mojallal, Seyed Ahmad, and Trevisan, Vilmar
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *GRAPH theory , *DISTRIBUTION (Probability theory) , *NUMBER theory - Abstract
Let G be a graph of order n with m edges and clique number ω . Let μ 1 ≥ μ 2 ≥ … ≥ μ n = 0 be the Laplacian eigenvalues of G and let σ = σ ( G ) ( 1 ≤ σ ≤ n ) be the largest positive integer such that μ σ ≥ 2 m n . In this paper we study the relation between σ and ω . In particular, we provide the answer to Problem 2.3 raised in Pirzada and Ganie (2015) [15] . Moreover, we characterize all connected threshold graphs with σ < ω − 1 , σ = ω − 1 and σ > ω − 1 . We obtain Nordhaus–Gaddum-type results for σ . Some relations between σ with other graph invariants are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
13. Characterization of extremal graphs from distance signless Laplacian eigenvalues.
- Author
-
Lin, Huiqiu and Das, Kinkar Ch.
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *EXTREMAL problems (Mathematics) , *GEOMETRIC vertices , *GRAPH theory - Abstract
Let G = ( V , E ) be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The transmission Tr ( v i ) of vertex v i is defined to be the sum of distances from v i to all other vertices. Let Tr ( G ) be the n × n diagonal matrix with its ( i , i ) -entry equal to Tr G ( v i ) . The distance signless Laplacian is defined as D Q ( G ) = Tr ( G ) + D ( G ) , where D ( G ) is the distance matrix of G . Let ∂ 1 ( G ) ≥ ∂ 2 ( G ) ≥ ⋯ ≥ ∂ n ( G ) denote the eigenvalues of distance signless Laplacian matrix of G . In this paper, we first characterize all graphs with ∂ n ( G ) = n − 2 . Secondly, we characterize all graphs with ∂ 2 ( G ) ∈ [ n − 2 , n ] when n ≥ 11 . Furthermore, we give the lower bound on ∂ 2 ( G ) with independence number α and the extremal graph is also characterized. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
14. The number of spanning trees of a graph with given matching number.
- Author
-
Feng, Lihua, Xu, Kexiang, Das, Kinkar Ch., Ilić, Aleksandar, and Yu, Guihai
- Subjects
NUMBER theory ,SPANNING trees ,MATHEMATICAL bounds ,LAPLACIAN matrices ,MATHEMATICAL models - Abstract
The number of spanning trees of a graphGis the total number of distinct spanning subgraphs ofGthat are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
15. Complete split graph determined by its (signless) Laplacian spectrum.
- Author
-
Das, Kinkar Ch. and Liu, Muhuo
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *TOPOLOGY , *COMBINATORICS , *MATHEMATICAL models - Abstract
A complete split graph C S ( n , α ) , is a graph on n vertices consisting of a clique on n − α vertices and an independent set on the remaining α ( 1 ≤ α ≤ n − 1 ) vertices in which each vertex of the clique is adjacent to each vertex of the independent set. In this paper, we prove that C S ( n , α ) is determined by its Laplacian spectrum when 1 ≤ α ≤ n − 1 , and C S ( n , α ) is also determined by its signless Laplacian spectrum when 1 ≤ α ≤ n − 1 and α ≠ 3 . [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
16. Relation between signless Laplacian energy, energy of graph and its line graph.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *ABSOLUTE value , *MATHEMATICAL bounds , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
17. Extremal Laplacian energy of threshold graphs.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *GRAPH connectivity , *MATHEMATICAL bounds , *EIGENVALUES , *MATHEMATICAL analysis - Abstract
Let G be a connected threshold graph of order n with m edges and trace T . In this paper we give a lower bound on Laplacian energy in terms of n, m and T of G . From this we determine the threshold graphs with the first four minimal Laplacian energies. Moreover, we obtain the threshold graphs with the largest and the second largest Laplacian energies. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
18. On energy and Laplacian energy of bipartite graphs.
- Author
-
Das, Kinkar Ch., Mojallal, Seyed Ahmad, and Gutman, Ivan
- Subjects
- *
LAPLACIAN matrices , *BIPARTITE graphs , *GRAPH theory , *EIGENVALUES , *ABSOLUTE value , *MATHEMATICAL bounds - Abstract
Let G be a bipartite graph of order n with m edges. The energy E ( G ) of G is the sum of the absolute values of the eigenvalues of the adjacency matrix A . In 1974, one of the present authors established lower and upper bounds for E ( G ) in terms of n, m , and det A . Now, more than 40 years later, we correct some details of this result and determine the extremal graphs. In addition, an upper bound on the Laplacian energy of bipartite graphs in terms of n, m , and the first Zagreb index is obtained, and the extremal graphs characterized. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
19. Bounds on the entries of the principal eigenvector of the distance signless Laplacian matrix.
- Author
-
Das, Kinkar Ch., da Silva Junior, Celso M., de Freitas, Maria Aguieiras A., and Del-Vecchio, Renata R.
- Subjects
- *
MATHEMATICAL bounds , *EIGENVECTORS , *LAPLACIAN matrices , *RADIUS (Geometry) , *EIGENVALUES , *MAXIMAL subgroups , *DIAMETER - Abstract
The distance signless Laplacian spectral radius of a connected graph G is the largest eigenvalue of the distance signless Laplacian matrix of G , defined as D Q ( G ) = T r ( G ) + D ( G ) , where D ( G ) is the distance matrix of G and T r ( G ) is the diagonal matrix of vertex transmissions of G . In this paper we determine upper and lower bounds on the minimal and maximal entries of the principal eigenvector of D Q ( G ) and characterize the extremal graphs. In addition, we obtain a lower bound on the distance signless Laplacian spectral radius of G based on its order and independence number, and characterize the extremal graph. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
20. On Laplacian energy in terms of graph invariants.
- Author
-
Das, Kinkar Ch., Mojallal, Seyed Ahmad, and Gutman, Ivan
- Subjects
- *
LAPLACIAN matrices , *INVARIANTS (Mathematics) , *GEOMETRIC vertices , *EDGES (Geometry) , *EIGENVALUES - Abstract
For G being a graph with n vertices and m edges, and with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n − 1 ≥ μ n = 0 , the Laplacian energy is defined as L E = ∑ i = 1 n | μ i − 2 m / n | . Let σ be the largest positive integer such that μ σ ≥ 2 m / n . We characterize the graphs satisfying σ = n − 1 . Using this, we obtain lower bounds for LE in terms of n, m , and the first Zagreb index. In addition, we present some upper bounds for LE in terms of graph invariants such as n, m , maximum degree, vertex cover number, and spanning tree packing number. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
21. Characterization of extremal graphs from Laplacian eigenvalues and the sum of powers of the Laplacian eigenvalues of graphs.
- Author
-
Chen, Xiaodan and Das, Kinkar Ch.
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *GRAPH theory , *GEOMETRIC vertices , *MEASUREMENT of angles (Geometry) - Abstract
For any real number α , let s α ( G ) denote the sum of the α th power of the non-zero Laplacian eigenvalues of a graph G . In this paper, we first obtain sharp bounds on the largest and the second smallest Laplacian eigenvalues of a graph, and a new spectral characterization of a graph from its Laplacian eigenvalues. Using these results, we then establish sharp bounds for s α ( G ) in terms of the number of vertices, number of edges, maximum vertex degree and minimum vertex degree of the graph G , from which a Nordhaus–Gaddum type result for s α is also deduced. Moreover, we characterize the graphs maximizing s α for α > 1 among all the connected graphs with given matching number. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
22. The Kirchhoff Index of Quasi-Tree Graphs.
- Author
-
Xu, Kexiang, Liu, Hongshuang, and Das, Kinkar Ch.
- Subjects
GRAPH connectivity ,TREE graphs ,GEOMETRIC vertices ,LAPLACIAN matrices ,GRAPH theory ,DECISION trees - Abstract
Resistance distance was introduced by Klein and Randić as a generalisation of the classical distance. The Kirchhoff index Kf(G) of a graph G is the sum of resistance distances between all unordered pairs of vertices. In this article we characterise the extremal graphs with the maximal Kirchhoff index among all non-trivial quasi-tree graphs of order n. Moreover, we obtain a lower bound on the Kirchhoff index for all non-trivial quasi-tree graphs of order n. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
23. Proof of conjectures on the distance signless Laplacian eigenvalues of graphs.
- Author
-
Das, Kinkar Ch.
- Subjects
- *
MATHEMATICAL proofs , *EIGENVALUES , *LAPLACIAN matrices , *GRAPH theory , *MATHEMATICAL models - Abstract
Let G = ( V , E ) be a simple graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The distance signless Laplacian spectral radius of a connected graph G is the spectral radius of the distance signless Laplacian matrix of G , defined as Q ( G ) = Tr ( G ) + D ( G ) , where Tr ( G ) is the diagonal matrix of vertex transmissions of G and D ( G ) is the distance matrix of G . In [10] , Xing et al. determined the graph with minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. For n ≥ 3 , let T n − 3 , 1 1 be the n -vertex tree of maximum degree n − 2 . In this paper, we show that T n − 3 , 1 1 gives the second minimum distance signless Laplacian spectral radius among the trees with fixed number of vertices. Moreover, we prove two conjectures involving the second largest eigenvalue of the distance signless Laplacian matrix Q ( G ) of graph G . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
24. Upper bounds on the (signless) Laplacian eigenvalues of graphs.
- Author
-
Das, Kinkar Ch., Liu, Muhuo, and Shan, Haiying
- Subjects
- *
MATHEMATICAL bounds , *LAPLACIAN matrices , *EIGENVALUES , *GRAPH theory , *SET theory - Abstract
Let G be a simple graph of order n with vertex set V = { v 1 , v 2 , … , v n } . Also let μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n − 1 ( G ) ≥ μ n ( G ) = 0 and q 1 ( G ) ≥ q 2 ( G ) ≥ ⋯ ≥ q n ( G ) ≥ 0 be the Laplacian eigenvalues and signless Laplacian eigenvalues of G , respectively. In this paper we obtain μ i ( G ) ≤ i − 1 + min U i max { | N H ( v k ) ∪ N H ( v j ) | : v k v j ∈ E ( H ) } , where N H ( v k ) is the set of neighbors of vertex v k in V ( H ) = V ( G ) \ U i , U i is any ( i − 1 ) -subset of V ( G ) (here, we agree that i ∈ { 1 , … , n − 1 } and μ i ( G ) ≤ i − 1 if E ( H ) = ∅ ). For any graph G , this bound does not exceed the order of G . Moreover, we prove that max { μ i ( G ) , q i ( G ) } ≤ max i ≤ k ≤ n { d G ( v k ) + ∑ v j ∈ N G ( v k ) ∩ N d G ( v j ) d G ( v k ) } ≤ 2 d G ( v i ) , where d G ( v i ) is the i -th largest degree of G and N = { v i , v i + 1 , … , v n } . [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
25. On Laplacian energy of graphs.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *EIGENVALUES , *MATHEMATICAL bounds , *INVARIANTS (Mathematics) , *NUMBER theory - Abstract
Abstract: Let be a graph with vertices and edges. Also let be the eigenvalues of the Laplacian matrix of graph . The Laplacian energy of the graph is defined as In this paper, we present some lower and upper bounds for of graph in terms of , the number of edges and the maximum degree . Also we give a Nordhaus–Gaddum-type result for Laplacian energy of graphs. Moreover, we obtain a relation between Laplacian energy and Laplacian-energy-like invariant of graphs. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
26. On the Laplacian-energy-like invariant.
- Author
-
Das, Kinkar Ch., Gutman, Ivan, and Çevik, A. Sinan
- Subjects
- *
LAPLACIAN matrices , *INVARIANTS (Mathematics) , *GRAPH connectivity , *GRAPH theory , *EIGENVALUES , *MATHEMATICAL bounds , *NUMBER theory - Abstract
Abstract: Let G be a connected graph of order n with Laplacian eigenvalues . The Laplacian-energy-like invariant of the graph G is defined as Lower and upper bounds for LEL are obtained, in terms of n, number of edges, maximum vertex degree, and number of spanning trees. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
27. On sum of powers of the Laplacian eigenvalues of graphs.
- Author
-
Das, Kinkar Ch., Xu, Kexiang, and Liu, Muhuo
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *GRAPH theory , *SET theory , *REAL numbers , *INVARIANTS (Mathematics) - Abstract
Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Let be the Laplacian eigenvalues of G. For a graph G and a real number , the graph invariant is the sum of the β-th power of the non-zero Laplacian eigenvalues of G, that is, In this paper, we obtain some lower and upper bounds on for G in terms of n, the number of edges m, maximum degree , clique number ω, independence number α and the number of spanning trees t. Moreover, we present some Nordhaus–Gaddum-type results for of G. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
28. Proof of conjectures involving algebraic connectivity of graphs
- Author
-
Das, Kinkar Ch.
- Subjects
- *
LOGICAL prediction , *GRAPH theory , *SET theory , *LAPLACIAN matrices , *EIGENVALUES , *MATHEMATICAL bounds - Abstract
Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity of a graph [18]. In this paper we give a lower bound on the algebraic connectivity of graphs. Moreover, we mention two conjectures, obtained by the system AutoGraphiX, about the algebraic connectivity , diameter and the minimum degree of graphs (see, [2], available online at http://www.gerad.ca/∼agx/):with equality if and only if G is isomorphic to a graph with and , and (ii) is minimum for a graph composed of 2 cliques on vertices with a common vertex if n is odd, and linked by an edge if n is even. Here we prove conjecture in (i) using the lower bound on the algebraic connectivity of graphs and conjecture in (ii), respectively. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
29. Laplacian eigenvalues of the second power of a graph
- Author
-
Das, Kinkar Ch. and Guo, Ji-Ming
- Subjects
- *
LAPLACIAN matrices , *EIGENVALUES , *GRAPH theory , *SET theory , *MATHEMATICAL bounds , *RADIUS (Geometry) - Abstract
Abstract: The power of a graph , denoted by , is the graph with the same vertex set as , such that two vertices are adjacent in if and only if their distance is at most in . In this paper, we give bounds on the first two largest Laplacian eigenvalues of the second power of a general graph, and on the second power of a tree. We also give a Nordhaus–Gaddum-type inequality for the Laplacian spectral radius of . [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
30. Sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph
- Author
-
Dilek (Güngör) Maden, A., Das, Kinkar Ch., and Sinan Çevik, A.
- Subjects
- *
LAPLACIAN matrices , *MATHEMATICAL bounds , *RADIUS (Geometry) , *SPECTRAL theory , *GRAPH connectivity , *TOPOLOGICAL degree - Abstract
Abstract: Let be a simple connected graph. Denote by the diagonal matrix of its vertex degrees and by its adjacency matrix. Then the signless Laplacian matrix of G is . In this paper, we obtain some new and improved sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph G. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
31. Sharp Bounds on (Generalized) Distance Energy of Graphs.
- Author
-
Alhevaz, Abdollah, Baghipur, Maryam, Das, Kinkar Ch., and Shang, Yilun
- Subjects
LAPLACIAN matrices ,GRAPH connectivity ,DISTANCES ,REGULAR graphs - Abstract
Given a simple connected graph G, let D (G) be the distance matrix, D L (G) be the distance Laplacian matrix, D Q (G) be the distance signless Laplacian matrix, and T r (G) be the vertex transmission diagonal matrix of G. We introduce the generalized distance matrix D α (G) = α T r (G) + (1 − α) D (G) , where α ∈ [ 0 , 1 ] . Noting that D 0 (G) = D (G) , 2 D 1 2 (G) = D Q (G) , D 1 (G) = T r (G) and D α (G) − D β (G) = (α − β) D L (G) , we reveal that a generalized distance matrix ideally bridges the spectral theories of the three constituent matrices. In this paper, we obtain some sharp upper and lower bounds for the generalized distance energy of a graph G involving different graph invariants. As an application of our results, we will be able to improve some of the recently given bounds in the literature for distance energy and distance signless Laplacian energy of graphs. The extremal graphs of the corresponding bounds are also characterized. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
32. Some graphs determined by their (signless) Laplacian spectra.
- Author
-
Liu, Muhuo, Shan, Haiying, and Das, Kinkar Ch.
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *ALGEBRA , *MATHEMATICAL analysis , *ISOMORPHISM (Mathematics) - Abstract
Abstract: A graph G is L–DS (respectively, Q–DS) if there is no other non-isomorphic graph with the same (respectively, signless) Laplacian spectrum as G. Let be the join graph of graphs and , and the graph obtained by attaching pendent vertices to a vertex of (the cycle of order r). In this paper, we prove that if G is L–DS and the algebraic connectivity of G is less than three, then is L–DS under certain condition, which extends the main result of Zhou and Bu (2012) [24]. Also, is proved to be Q–DS for . [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.