Displaying similar documents to “Fires on trees”

Bounds for the number of meeting edges in graph partitioning

Qinghou Zeng, Jianfeng Hou (2017)

Czechoslovak Mathematical Journal

Similarity:

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least ( w 1 - Δ 1 ) / 2 + 2 w 2 / 3 , where w i is the total weight of edges of size i and Δ 1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least ( w 0 - 1 ) / 6 + ( w 1 - Δ 1 ) / 3 + 2 w 2 / 3 , where...

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

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

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

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

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

Characterizing finite groups whose enhanced power graphs have universal vertices

David G. Costanzo, Mark L. Lewis, Stefano Schmidt, Eyob Tsegaye, Gabe Udell (2024)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite group and construct a graph Δ ( G ) by taking G { 1 } as the vertex set of Δ ( G ) and by drawing an edge between two vertices x and y if x , y is cyclic. Let K ( G ) be the set consisting of the universal vertices of Δ ( G ) along the identity element. For a solvable group G , we present a necessary and sufficient condition for K ( G ) to be nontrivial. We also develop a connection between Δ ( G ) and K ( G ) when | G | is divisible by two distinct primes and the diameter of Δ ( G ) is 2.

On g c -colorings of nearly bipartite graphs

Yuzhuo Zhang, Xia Zhang (2018)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple graph, let d ( v ) denote the degree of a vertex v and let g be a nonnegative integer function on V ( G ) with 0 g ( v ) d ( v ) for each vertex v V ( G ) . A g c -coloring of G is an edge coloring such that for each vertex v V ( G ) and each color c , there are at least g ( v ) edges colored c incident with v . The g c -chromatic index of G , denoted by χ g c ' ( G ) , is the maximum number of colors such that a g c -coloring of G exists. Any simple graph G has the g c -chromatic index equal to δ g ( G ) or δ g ( G ) - 1 , where δ g ( G ) = min v V ( G ) d ( v ) / g ( v ) . A graph G is nearly bipartite,...

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