Extremal trees and molecular trees with respect to the Sombor-index-like graph invariants $\mathcal {SO}_5$ and $\mathcal {SO}_6$

Wei Gao

Displaying similar documents to “Extremal trees and molecular trees with respect to the Sombor-index-like graph invariants $\mathcal {SO}_5$ and $\mathcal {SO}_6$”

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 \leq γ_{2, 2} (T) \leq 2 γ (T)$ . Moreover, we characterize all the trees achieving the equalities.

Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu (2015)

Colloquium Mathematicae

Similarity:

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = v ₀, v ₁, . . ., v_{n - 1}$ , $E ₁ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}$ and $E ₂ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 3} v_{n - 2}, v_{n - 3} v_{n - 1}$ . For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r (T ₘ, T ₙ^{i})$ , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

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 $\sqrt{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 \in 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 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...

Extremal properties of distance-based graph invariants for $k$ -trees

Minjie Zhang, Shuchao Li (2018)

Mathematica Bohemica

Similarity:

Sharp bounds on some distance-based graph invariants of $n$ -vertex $k$ -trees are established in a unified approach, which may be viewed as the weighted Wiener index or weighted Harary index. The main techniques used in this paper are graph transformations and mathematical induction. Our results demonstrate that among $k$ -trees with $n$ vertices the extremal graphs with the maximal and the second maximal reciprocal sum-degree distance are coincident with graphs having the maximal and the second...

The instability of nonseparable complete Erdős spaces and representations in ℝ-trees

Jan J. Dijkstra, Kirsten I. S. Valkenburg (2010)

Fundamenta Mathematicae

Similarity:

One way to generalize complete Erdős space $_{c}$ is to consider uncountable products of zero-dimensional $G_{δ}$ -subsets of the real line, intersected with an appropriate Banach space. The resulting (nonseparable) complete Erdős spaces can be fully classified by only two cardinal invariants, as done in an earlier paper of the authors together with J. van Mill. As we think this is the correct way to generalize the concept of complete Erdős space to a nonseparable setting, natural questions arise...

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

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 \subseteq 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 \subseteq 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 \subseteq V (G)$ and $| S | \geq 2$ , the pendant tree-connectivity $τ_{G} (S)$ is the maximum number of internally disjoint pendant $S$ -Steiner trees in $G$ , and for $k \geq 2$ , the $k$ -pendant tree-connectivity $τ_{k} (G)$ is the...

The tree property at both $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$

Laura Fontanella, Sy David Friedman (2015)

Fundamenta Mathematicae

Similarity:

We force from large cardinals a model of ZFC in which $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$ both have the tree property. We also prove that if we strengthen the large cardinal assumptions, then in the final model $ℵ_{ω + 2}$ even satisfies the super tree property.

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

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal graphs.

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

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 \sum_{u, v \in 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})) \leq W (μ (T ₙ^{k})) \leq 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})$ .