Displaying similar documents to “Signpost systems and spanning trees of graphs”

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with d e g G u + d e g G v ≥ n - 1 , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on d e g G u + d e g G v and the structure of the distant area for u and v. We prove...

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and γ 2 , 2 ( G ) denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that ( 2 ( γ ( T ) + 1 ) ) / 3 ≤ γ 2 , 2 ( T ) ≤ 2 γ ( T ) . Moreover, we characterize all the trees achieving the equalities.

A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

Similarity:

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 n vertices, n ≥ 1 , is n . The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice...

Extremal trees and molecular trees with respect to the Sombor-index-like graph invariants 𝒮𝒪 5 and 𝒮𝒪 6

Wei Gao (2024)

Czechoslovak Mathematical Journal

Similarity:

I. Gutman (2022) constructed six new graph invariants based on geometric parameters, and named them Sombor-index-like graph invariants, denoted by 𝒮𝒪 1 , 𝒮𝒪 2 , ⋯ , 𝒮𝒪 6 . Z. Tang, H. Deng (2022) and Z. Tang, Q. Li, H. Deng (2023) investigated the chemical applicability and extremal values of these Sombor-index-like graph invariants, and raised some open problems, see Z. Tang, Q. Li, H. Deng (2023). We consider the first open problem formulated at the end of Z. Tang, Q. Li, H. Deng (2023). We obtain the extremal...

The induced paths in a connected graph and a ternary relation determined by them

Ladislav Nebeský (2002)

Mathematica Bohemica

Similarity:

By a ternary structure we mean an ordered pair ( X 0 , T 0 ) , where X 0 is a finite nonempty set and T 0 is a ternary relation on X 0 . By the underlying graph of a ternary structure ( X 0 , T 0 ) we mean the (undirected) graph G with the properties that X 0 is its vertex set and distinct vertices u and v of G are adjacent if and only if { x ∈ X 0 T 0 ( u , x , v ) } ∪ { x ∈ X 0 T 0 ( v , x , u ) } = { u , v } . A ternary structure ( X 0 , T 0 ) is said to be the B-structure of a connected graph G if X 0 is the vertex set of G and the following statement holds for all u , x , y ∈ X 0 : T 0 ( x , u , y ) if and only if u belongs to an...

The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan, S. Francis Raj (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The Wiener number of a graph G is defined as 1 / 2 ∑ u , v ∈ V ( G ) d ( u , v ) , d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, W ( μ ( S ₙ k ) ) ≤ W ( μ ( T ₙ k ) ) ≤ W ( μ ( P ₙ k ) ) , where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of μ ( G k ) .