All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 31

Showing per page

Decompositions into two paths

Zdzisław Skupień (2005)

Discussiones Mathematicae Graph Theory

It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each n ≥ 3. The...

Decompositions of quadrangle-free planar graphs

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh (2009)

Discussiones Mathematicae Graph Theory

W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.

Diameter-invariant graphs

Ondrej Vacek (2005)

Mathematica Bohemica

The diameter of a graph G is the maximal distance between two vertices of  G . A graph G is said to be diameter-edge-invariant, if d ( G - e ) = d ( G ) for all its edges, diameter-vertex-invariant, if d ( G - v ) = d ( G ) for all its vertices and diameter-adding-invariant if d ( G + e ) = d ( e ) for all edges of the complement of the edge set of G . This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.

Distance in graphs

Roger C. Entringer, Douglas E. Jackson, D. A. Snyder (1976)

Czechoslovak Mathematical Journal

Currently displaying 1 – 20 of 31

Page 1 Next