The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

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.