Displaying similar documents to “On k -pairable graphs from trees”

Arbitrarily vertex decomposable caterpillars with four or five leaves

Sylwia Cichacz, Agnieszka Görlich, Antoni Marczyk, Jakub Przybyło, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, V i induces a connected subgraph of G on a i vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable...

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 δ ≥ 1 2 ( L ( G ) + 1 ) , then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ≥ 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....

Classifying trees with edge-deleted central appendage number 2

Shubhangi Stalder, Linda Eroh, John Koker, Hosien S. Moghadam, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

The eccentricity of a vertex v of a connected graph G is the distance from v to a vertex farthest from v in G . The center of G is the subgraph of G induced by the vertices having minimum eccentricity. For a vertex v in a 2-edge-connected graph G , the edge-deleted eccentricity of v is defined to be the maximum eccentricity of v in G - e over all edges e of G . The edge-deleted center of G is the subgraph induced by those vertices of G having minimum edge-deleted eccentricity. The edge-deleted...

The 3-path-step operator on trees and unicyclic graphs

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

E. Prisner in his book Graph Dynamics defines the k -path-step operator on the class of finite graphs. The k -path-step operator (for a positive integer k ) is the operator S k ' which to every finite graph G assigns the graph S k ' ( G ) which has the same vertex set as G and in which two vertices are adjacent if and only if there exists a path of length k in G connecting them. In the paper the trees and the unicyclic graphs fixed in the operator S 3 ' are studied.