The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs”

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

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

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

Quasi-tree graphs with the minimal Sombor indices

Yibo Li, Huiqing Liu, Ruiting Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

The Sombor index S O ( G ) of a graph G is the sum of the edge weights d G 2 ( u ) + d G 2 ( v ) of all edges u v of G , where d G ( u ) denotes the degree of the vertex u in G . A connected graph G = ( V , E ) is called a quasi-tree if there exists u V ( G ) such that G - u is a tree. Denote 𝒬 ( n , k ) = { G : G is a quasi-tree graph of order n with G - u being a tree and d G ( u ) = k } . We determined the minimum and the second minimum Sombor indices of all quasi-trees in 𝒬 ( n , k ) . Furthermore, we characterized the corresponding extremal graphs, respectively.

On the tree structure of the power digraphs modulo n

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

Similarity:

For any two positive integers n and k 2 , let G ( n , k ) be a digraph whose set of vertices is { 0 , 1 , ... , n - 1 } and such that there is a directed edge from a vertex a to a vertex b if a k b ( mod n ) . Let n = i = 1 r p i e i be the prime factorization of n . Let P be the set of all primes dividing n and let P 1 , P 2 P be such that P 1 P 2 = P and P 1 P 2 = . A fundamental constituent of G ( n , k ) , denoted by G P 2 * ( n , k ) , is a subdigraph of G ( n , k ) induced on the set of vertices which are multiples of p i P 2 p i and are relatively prime to all primes q P 1 . L. Somer and M. Křížek proved that the trees attached...

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