Vertex-Generator Subgraphs of Complete Bipartite and Tadpole Graphs

Abstract

Graphs considered in this paper are finite simple undirected graphs. Let $G = (V(G), E(G))$ be a graph with the vertex set $V(G) = \{x_1,x_2,..., x_n\}$, for some positive integer $n$. The vertex space $\mathscr{V}(G)$ of $G$, is a vector space over the field $\mathbb{Z}_2 = \{0,1\}$. The elements of $\mathscr{V}(G)$ are all the subsets of $V(G)$. Vector addition is defined as $A + B = A \:\triangle\: B$, the symmetric difference of sets $A$ and $B$, for all $A,B \in \mathscr{V}(G)$. Scalar multiplication is defined as $1 \cdot A = A$ and $0 \cdot A = \emptyset$, for all $A \in \mathscr{V}(G)$. The subgraph $G \langle S \rangle$ of $G$ induced by a subset $S$ of $V(G)$, is the largest subgraph whose vertex set is $S$. The vertex-uniform set $V_H(G)$ of a subgraph $H$ with respect to $G$, is the set of all elements of $\mathscr{V}(G)$ that induces a subgraph isomorphic to $H$. The span of $V_H(G)$ shall be denoted by $\mathscr{V}_H(G)$. If $V_H(G)$ is a generating set, that is $\mathscr{V}_H(G) = \mathscr{V}(G)$, then $H$ is called a vertex-generator subgraph of $G$. This study determines some vertex-generator subgraphs of complete bipartite graph $K_{m,n}$ and tadpole graph $T_{n,m}$.