Displaying similar documents to “Turán's problem and Ramsey numbers for trees”

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

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

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.

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

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with n vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate n - α on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as n , the terminal density of fireproof...

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

Note on improper coloring of 1 -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph G = ( V , E ) is called improperly ( d 1 , , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , , V k such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most d i for all 1 i k . In this paper, we mainly study the improper coloring of 1 -planar graphs and show that 1 -planar graphs with girth at least 7 are ( 2 , 0 , 0 , 0 ) -colorable.

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.

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

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

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 .