Displaying similar documents to “Quasi-tree graphs with the minimal Sombor indices”

On a characterization of k -trees

De-Yan Zeng, Jian Hua Yin (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a k -tree if either G is the complete graph on k + 1 vertices, or G has a vertex v whose neighborhood is a clique of order k and the graph obtained by removing v from G is also a k -tree. Clearly, a k -tree has at least k + 1 vertices, and G is a 1-tree (usual tree) if and only if it is a 1 -connected graph and has no K 3 -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of k -trees as follows: if G is a graph with at least k + 1 vertices, then G is...

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

Similarity:

For a connected graph G = ( V , E ) and a set S V ( G ) with at least two vertices, an S -Steiner tree is a subgraph T = ( V ' , E ' ) of G that is a tree with S V ' . If the degree of each vertex of S in T is equal to 1, then T is called a pendant S -Steiner tree. Two S -Steiner trees are if they share no vertices other than S and have no edges in common. For S V ( G ) and | S | 2 , the pendant tree-connectivity τ G ( S ) is the maximum number of internally disjoint pendant S -Steiner trees in G , and for k 2 , the k -pendant tree-connectivity τ k ( G ) is the...

The relation between the number of leaves of a tree and its diameter

Pu Qiao, Xingzhi Zhan (2022)

Czechoslovak Mathematical Journal

Similarity:

Let L ( n , d ) denote the minimum possible number of leaves in a tree of order n and diameter d . Lesniak (1975) gave the lower bound B ( n , d ) = 2 ( n - 1 ) / d for L ( n , d ) . When d is even, B ( n , d ) = L ( n , d ) . But when d is odd, B ( n , d ) is smaller than L ( n , d ) in general. For example, B ( 21 , 3 ) = 14 while L ( 21 , 3 ) = 19 . In this note, we determine L ( n , d ) using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha, Dang Dinh Hanh, Nguyen Thanh Loan, Ngoc Diep Pham (2021)

Czechoslovak Mathematical Journal

Similarity:

Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T . The set of leaves of T is denoted by L ( T ) and the set of branch vertices of T is denoted by B ( T ) . For two distinct vertices u , v of T , let P T [ u , v ] denote the unique path in T connecting u and v . Let T be a tree with B ( T ) . For each leaf x of T , let y x denote the nearest branch vertex to x . We delete V ( P T [ x , y x ] ) { y x } from T for all x L ( T ) . The resulting subtree of T is called the reducible stem...

On γ-labelings of trees

Gary Chartrand, David Erwin, Donald W. VanderJagt, Ping Zhang (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is v a l ( f ) = Σ e E ( G ) f ' K ( e ) . The maximum value of a γ-labeling of G is defined as v a l m a x ( G ) = m a x v a l ( f ) : f i s a γ - l a b e l i n g o f G ; while the minimum value of a γ-labeling of G is v a l m i n ( G ) = m i n v a l ( f ) : f i s a γ - l a b e l i n g o f G ; The values v a l m a x ( S p , q ) and v a l m i n ( S p , q ) are determined for double stars S p , q . We present characterizations of connected graphs G of order n for which...

On graceful colorings of trees

Sean English, Ping Zhang (2017)

Mathematica Bohemica

Similarity:

A proper coloring c : V ( G ) { 1 , 2 , ... , k } , k 2 of a graph G is called a graceful k -coloring if the induced edge coloring c ' : E ( G ) { 1 , 2 , ... , k - 1 } defined by c ' ( u v ) = | c ( u ) - c ( v ) | for each edge u v of G is also proper. The minimum integer k for which G has a graceful k -coloring is the graceful chromatic number χ g ( G ) . It is known that if T is a tree with maximum degree Δ , then χ g ( T ) 5 3 Δ and this bound is best possible. It is shown for each integer Δ 2 that there is an infinite class of trees T with maximum degree Δ such that χ g ( T ) = 5 3 Δ . In particular, we investigate for each...

Horocyclic products of trees

Laurent Bartholdi, Markus Neuhauser, Wolfgang Woess (2008)

Journal of the European Mathematical Society

Similarity:

Let T 1 , , T d be homogeneous trees with degrees q 1 + 1 , , q d + 1 3 , respectively. For each tree, let 𝔥 : T j be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of T 1 , , T d is the graph 𝖣𝖫 ( q 1 , , q d ) consisting of all d -tuples x 1 x d T 1 × × T d with 𝔥 ( x 1 ) + + 𝔥 ( x d ) = 0 , equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If d = 2 and q 1 = q 2 = q then we obtain a Cayley graph...

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...

Distance matrices perturbed by Laplacians

Balaji Ramamurthy, Ravindra Bhalchandra Bapat, Shivani Goel (2020)

Applications of Mathematics

Similarity:

Let T be a tree with n vertices. To each edge of T we assign a weight which is a positive definite matrix of some fixed order, say, s . Let D i j denote the sum of all the weights lying in the path connecting the vertices i and j of T . We now say that D i j is the distance between i and j . Define D : = [ D i j ] , where D i i is the s × s null matrix and for i j , D i j is the distance between i and j . Let G be an arbitrary connected weighted graph with n vertices, where each weight is a positive definite matrix of order...

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 .

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 ...

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let G 1 and G 2 be two given graphs. The Ramsey number R ( G 1 , G 2 ) is the least integer r such that for every graph G on r vertices, either G contains a G 1 or G ¯ contains a G 2 . Parsons gave a recursive formula to determine the values of R ( P n , K 1 , m ) , where P n is a path on n vertices and K 1 , m is a star on m + 1 vertices. In this note, we study the Ramsey numbers R ( P n , K 1 F m ) , where F m is a linear forest on m vertices. We determine the exact values of R ( P n , K 1 F m ) for the cases m n and m 2 n , and for the case that F m has no odd component. Moreover, we...