Inductive classes of bipartite cubic graphs

✍ Scribed by Vladimir Batagelj

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 269 KB
• Volume: 134
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0055-9

✦ Synopsis

In the paper two (a local and an expanding) inductive definitions of the class of all simple connected bipartite cubic graphs are given.

0. ~n~~uction

We shall use the notions and notations from [l, 31. An inductive definition of a class Cn(S?'; 9) is local iff for each rule from 9 the part of the graph on the left side of the rule is connected; and is expcrnding iff the application of each rule increases the size (number of vertices, number of edges, . . .) of the graph. In the paper two (one local and one expanding) inductive definitions of the class of al1 (simple, connected) bipartite cubic graphs are given. There already exist inductive definitions of the following subclasses of this class:

l planar bipartite cubic graphs [l]; and l planar j-connected bipartite cubic graphs [2,4,6].

1. Local inductive definition of the class of bipartite cubic graphs

Theorem. The inductive class Cn(K,, 3; Pl, P2) (see Fig. ) is equal to the class GfB cfall (simple, connected) bipartite cubic graphs.

Proof. Because the basic graph K3,3 is a bipartite cubic graph and the rules Pl and P2 preserve both properties, by inductive generalization 4=Cn(K3, 3; Pl, P2)c:%?,.