Generator Subgraphs of the Wheel

Authors: Neil M. Mame

Abstract:

We consider only finite graphs without loops nor multiple edges. Let G be a graph with E(G) = {e1, e2, …., em}. The edge space of G, denoted by ε(G), is a vector space over the field Z2. The elements of ε(G) are all the subsets of E(G). Vector addition is defined as X+Y = X Δ Y, the symmetric difference of sets X and Y, for X, Y ∈ ε(G). Scalar multiplication is defined as 1.X =X and 0.X = Ø for X ∈ ε(G). The set S ⊆ ε(G) is called a generating set if every element ε(G) is a linear combination of the elements of S. For a non-empty set X ∈ ε(G), the smallest subgraph with edge set X is called edge-induced subgraph of G, denoted by G[X]. The set EH(G) = { A ∈ ε(G) : G[A] ≅ H } denotes the uniform set of H with respect to G and εH(G) denotes the subspace of ε(G) generated by EH(G). If εH(G) is generating set, then we call H a generator subgraph of G. This paper gives the characterization for the generator subgraphs of the wheel that contain cycles and gives the necessary conditions for the acyclic generator subgraphs of the wheel.

Keywords: edge space, edge-induced subgraph, generator subgraph, wheel