Displaying similar documents to “A complete grammar for decomposing a family of graphs into 3-connected components.”

Rainbow Connection In Sparse Graphs

Arnfried Kemnitz, Jakub Przybyło, Ingo Schiermeyer, Mariusz Woźniak (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-coloured connected graph G = (V,E) is called rainbow-connected if each pair of distinct vertices of G is connected by a path whose edges have distinct colours. The rainbow connection number of G, denoted by rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) ≤ k if |V (G)| = n and for all integers n and k with n − 6 ≤ k ≤ n − 3. We also show that this bound is tight.

On distances between isomorphism classes of graphs

Gerhard Benadé, Wayne Goddard, Terry A. McKee, Paul A. Winter (1991)

Mathematica Bohemica

Similarity:

In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.