Displaying similar documents to “On the bounds of Laplacian eigenvalues of k -connected graphs”

Inequalities for real number sequences with applications in spectral graph theory

Emina Milovanović, Şerife Burcu Bozkurt Altındağ, Marjan Matejić, Igor Milovanović (2022)

Czechoslovak Mathematical Journal

Similarity:

Let a = ( a 1 , a 2 , ... , a n ) be a nonincreasing sequence of positive real numbers. Denote by S = { 1 , 2 , ... , n } the index set and by J k = { I = { r 1 , r 2 , ... , r k } , 1 r 1 < r 2 < < r k n } the set of all subsets of S of cardinality k , 1 k n - 1 . In addition, denote by a I = a r 1 + a r 2 + + a r k , 1 k n - 1 , 1 r 1 < r 2 < < r k n , the sum of k arbitrary elements of sequence a , where a I 1 = a 1 + a 2 + + a k and a I n = a n - k + 1 + a n - k + 2 + + a n . We consider bounds of the quantities R S k ( a ) = a I 1 / a I n , L S k ( a ) = a I 1 - a I n and S k , α ( a ) = I J k a I α in terms of A = i = 1 n a i and B = i = 1 n a i 2 . Then we use the obtained results to generalize some results regarding Laplacian and normalized Laplacian eigenvalues of graphs.

On the multiplicity of Laplacian eigenvalues for unicyclic graphs

Fei Wen, Qiongxiang Huang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let G be a connected graph of order n and U a unicyclic graph with the same order. We firstly give a sharp bound for m G ( μ ) , the multiplicity of a Laplacian eigenvalue μ of G . As a straightforward result, m U ( 1 ) n - 2 . We then provide two graph operations (i.e., grafting and shifting) on graph G for which the value of m G ( 1 ) is nondecreasing. As applications, we get the distribution of m U ( 1 ) for unicyclic graphs on n vertices. Moreover, for the two largest possible values of m U ( 1 ) { n - 5 , n - 3 } , the corresponding graphs U are...

Some properties of generalized distance eigenvalues of graphs

Yuzheng Ma, Yan Ling Shao (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple connected graph with vertex set V ( G ) = { v 1 , v 2 , , v n } and edge set E ( G ) , and let d v i be the degree of the vertex v i . Let D ( G ) be the distance matrix and let T r ( G ) be the diagonal matrix of the vertex transmissions of G . The generalized distance matrix of G is defined as D α ( G ) = α T r ( G ) + ( 1 - α ) D ( G ) , where 0 α 1 . Let λ 1 ( D α ( G ) ) λ 2 ( D α ( G ) ) ... λ n ( D α ( G ) ) be the generalized distance eigenvalues of G , and let k be an integer with 1 k n . We denote by S k ( D α ( G ) ) = λ 1 ( D α ( G ) ) + λ 2 ( D α ( G ) ) + ... + λ k ( D α ( G ) ) the sum of the k largest generalized distance eigenvalues. The generalized distance spread of a graph G is defined as D α S ( G ) = λ 1 ( D α ( G ) ) - λ n ( D α ( G ) ) ....

On the signless Laplacian and normalized signless Laplacian spreads of graphs

Emina Milovanović, Serife B. Bozkurt Altindağ, Marjan Matejić, Igor Milovanović (2023)

Czechoslovak Mathematical Journal

Similarity:

Let G = ( V , E ) , V = { v 1 , v 2 , ... , v n } , be a simple connected graph with n vertices, m edges and a sequence of vertex degrees d 1 d 2 d n . Denote by A and D the adjacency matrix and diagonal vertex degree matrix of G , respectively. The signless Laplacian of G is defined as L + = D + A and the normalized signless Laplacian matrix as + = D - 1 / 2 L + D - 1 / 2 . The normalized signless Laplacian spreads of a connected nonbipartite graph G are defined as r ( G ) = γ 2 + / γ n + and l ( G ) = γ 2 + - γ n + , where γ 1 + γ 2 + γ n + 0 are eigenvalues of + . We establish sharp lower and upper bounds for the normalized signless...

Even factor of bridgeless graphs containing two specified edges

Nastaran Haghparast, Dariush Kiani (2018)

Czechoslovak Mathematical Journal

Similarity:

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let G be a bridgeless simple graph with minimum degree at least 3 . Jackson and Yoshimoto (2007) showed that G has an even factor containing two arbitrary prescribed edges. They also proved that G has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges e 1 and e 2 of G , there is an even factor containing e 1 and e 2 ...

The Turán number of the graph 3 P 4

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let e x ( n , G ) denote the maximum number of edges in a graph on n vertices which does not contain G as a subgraph. Let P i denote a path consisting of i vertices and let m P i denote m disjoint copies of P i . In this paper we count e x ( n , 3 P 4 ) .

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph G , denoted by L ( G ) , has E ( G ) as its vertex set, where two vertices in L ( G ) are adjacent if and only if the corresponding edges in G have a vertex in common. For a graph H , define σ ¯ 2 ( H ) = min { d ( u ) + d ( v ) : u v E ( H ) } . Let H be a 2-connected claw-free simple graph of order n with δ ( H ) 3 . We show that, if σ ¯ 2 ( H ) 1 7 ( 2 n - 5 ) and n is sufficiently large, then either H is traceable or the Ryjáček’s closure cl ( H ) = L ( G ) , where G is an essentially 2 -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

The small Ree group 2 G 2 ( 3 2 n + 1 ) and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let G be a finite group. The main supergraph 𝒮 ( G ) is a graph with vertex set G in which two vertices x and y are adjacent if and only if o ( x ) o ( y ) or o ( y ) o ( x ) . In this paper, we will show that G 2 G 2 ( 3 2 n + 1 ) if and only if 𝒮 ( G ) 𝒮 ( 2 G 2 ( 3 2 n + 1 ) ) . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group 2 G 2 ( 3 2 n + 1 ) .

Saturation numbers for linear forests P 6 + t P 2

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph G is H -saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G . The saturation number, sat ( n , H ) , is the minimum number of edges of a graph in the set of all H -saturated graphs of order n . We determine the saturation number sat ( n , P 6 + t P 2 ) for n 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized k -connectivity κ k ( G ) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k -edge-connectivity which is defined as λ k ( G ) = min { λ ( S ) : S V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number of pairwise edge-disjoint trees T 1 , T 2 , ... , T in G such that S V ( T i ) for 1 i . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G H ) λ 3 ( G ) + λ 3 ( H ) , where G H is the Cartesian product of G and H . Moreover, the bound is sharp. We also...

Matchings in complete bipartite graphs and the r -Lah numbers

Gábor Nyul, Gabriella Rácz (2021)

Czechoslovak Mathematical Journal

Similarity:

We give a graph theoretic interpretation of r -Lah numbers, namely, we show that the r -Lah number n k r counting the number of r -partitions of an ( n + r ) -element set into k + r ordered blocks is just equal to the number of matchings consisting of n - k edges in the complete bipartite graph with partite sets of cardinality n and n + 2 r - 1 ( 0 k n , r 1 ). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for r -Stirling numbers of the second kind. ...