Arbitrarily vertex decomposable caterpillars with four or five leaves

Sylwia Cichacz; Agnieszka Görlich; Antoni Marczyk; Jakub Przybyło; Mariusz Woźniak

Displaying similar documents to “Arbitrarily vertex decomposable caterpillars with four or five leaves”

On $k$ -pairable graphs from trees

Zhongyuan Che (2007)

Czechoslovak Mathematical Journal

Similarity:

The concept of the $k$ -pairable graphs was introduced by Zhibo Chen (On $k$ -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p (G)$ , called the pair length of a graph $G$ , as the maximum $k$ such that $G$ is $k$ -pairable and $p (G) = 0$ if $G$ is not $k$ -pairable for any positive integer $k$ . In this paper, we answer the two open questions raised by Chen in the case that the graphs...

Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning, Viroshan Naicker (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $γ_{t}^{d} (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...

A remark on branch weights in countable trees

Bohdan Zelinka (2004)

Mathematica Bohemica

Similarity:

Let $T$ be a tree, let $u$ be its vertex. The branch weight $b (u)$ of $u$ is the maximum number of vertices of a branch of $T$ at $u$ . The set of vertices $u$ of $T$ in which $b (u)$ attains its minimum is the branch weight centroid $B (T)$ of $T$ . For finite trees the present author proved that $B (T)$ coincides with the median of $T$ , therefore it consists of one vertex or of two adjacent vertices. In this paper we show that for infinite countable trees the situation is quite different.

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite connected graph with minimum degree $δ$ . The leaf number $L (G)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$ . We prove that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....

Coalescing Fiedler and core vertices

Didar A. Ali, John Baptist Gauci, Irene Sciriha, Khidir R. Sharaf (2016)

Czechoslovak Mathematical Journal

Similarity:

The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex...

On arbitrarily vertex decomposable unicyclic graphs with dominating cycle

Sylwia Cichacz, Irmina A. Zioło (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that $\sum_{i = 1}^{k} n_{i} = n$ , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set $V_{i}$ induces a connected subgraph of G on $n_{i}$ vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour. ...

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

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

Solution to the problem of Kubesa

Mariusz Meszka (2008)

Discussiones Mathematicae Graph Theory

Similarity:

An infinite family of T-factorizations of complete graphs $K_{2 n}$ , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{\times 2} (G)$ , is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{\times 2}$ -vertex critical graph ( $γ_{\times 2}$ -vertex stable graph, respectively) if the removal of any vertex different...