### A note on the generator subgraph of a graph

#### Abstract

Graphs considered in this paper are finite simple undirected graphs. Let *G* = (*V*(*G*), *E*(*G*)) be a graph with *E*(*G*) = {e_{1}, e_{2},..., e_{m}}, for some positive integer *m*. The *edge space* of *G*, denoted by ℰ(*G*), is a vector space over the field ℤ_{2}. 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*). Let H be a subgraph of *G*. The *uniform set of* *H* with respect to *G*, denoted by *E*_{H}(*G*), is the set of all elements of ℰ(*G*) that induces a subgraph isomorphic to *H*. The subspace of ℰ(*G*) generated by ℰ* _{H}*(

*G*) shall be denoted by ℰ

*(*

_{H}*G*). If

*E*(

_{H}*G*) is a generating set, that is ℰ

*(*

_{H}*G*)= ℰ(

*G*), then

*H*is called a

*generator subgraph*of

*G*. This study determines the dimension of subspace generated by the set of all subsets of

*E*(

*G*) with even cardinality and the subspace generated by the set of all

*k*-subsets of

*E*(

*G*), for some positive integer

*k*, 1 ≤

*k*≤

*m*. Moreover, this paper determines all the generator subgraphs of star graphs. Furthermore, it gives a characterization for a graph

*G*so that star is a generator subgraph of

*G*.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.3

#### References

G. Chartrand, and P. Zhang, Introduction to Graph Theory, Mc Graw Hill, Reading, Singa- pore, 2005.

S. V. Gervacio, Generator graphs, contributed paper, 4th International Conference On Combi- natorial Mathematics and Combinatorial Computing,U.A., New Zealand, Dec 15-19, 2008.

S. V. Gervacio , Determination of uniform generating sets of the edge space of some graphs, research project under URCO, De La Salle University-Manila, April 2009.

S. V. Gervacio & N. M. Mame, Universal and primitive graphs, Proc., Osaka University-De La Salle University Academic Research Workshop, Manila, August 2007, 51–53.

S. V. Gervacio , M. T. C. Valdez, & D. F. Bengo, Generator subgraphs of fans and wheels, Proc., Osaka University - De La Salle University Academic Research Workshop, Manila, August 2008.

S. Kavitha, R. Kala, On the genus of graphs from commutative rings, AKCE Int. J. Graphs Combin. 14 (2017), 27–34.

M. Klasar, Counting even and odd partitions, The Amer. Math. Monthly 110 (6), 527 – 532.

S. Maity, A. K. Bhuniya, On the spectrum of linear dependence graph of a finite dimensional vector space, Electron. J. Graph Theory Appl. 7 (1) (2019), 43–59.

E. D. Nering, Linear Algebra and Matrix Theory, 2nd ed., John Wiley & Sons, Reading, USA, 1970.

L. A. Ruivivar, Some generator subgraphs of the complete bipartite graph, Proc., 5th Asian Mathematical Conference, Malaysia, (2009), 516–520.

Shang, Yilun, Subgraph robustness of complex networks under attacks, IEEE Transactions on Systems, Man, and Cybernetics: Systems 49 (2019), 821–832.

E. Vatandoost, M. Khalili, Domination number of the non-commuting graph of finite groups, Electron. J. Graph Theory Appl. 6 (2) (2018), 228–237.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.