Graph-Induced Finite Near-Rings from Subgraph Spaces Over F₂

Graph-Induced Finite Near-Rings from Subgraph Spaces Over F2

(1) K. V Rama Rao (2) K. Anuradha

(1) Professor (2) Asst Professor Department of Mathematics

RK College of Engineering ,Vijayawada Andhra Pradesh-521456

Abstract

Graph theory and algebra are naturally connected through vector spaces associated with graphs. In particular, the edge set of a finite graph can be regarded as a vector space over the field IF = {0,1}, with symmetric difference (ring sum) serving as vector addition. This paper develops a systematic framework for finite graph- induced rings and near-rings. We first establish the vector-space structure of the edge-subset space and its cycle-space subspaces. We then construct Boolean rings of orders 2, 4, 8, and 16 using symmetric difference and intersection, and explain carefully why these examples are rings and hence special cases of near-rings. To obtain a broader near-ring viewpoint, we study transformation near-rings acting on graph subspaces, with pointwise addition and composition as multiplication. Explicit Cayley tables are given for the small graph-ring examples, and several theorems concerning closure, associativity, distributivity, finiteness, and cardinality are proved. The paper concludes with applications to digital logic, switching theory, finite automata, coding theory, and graph-based algebraic computation. The distinction between a graph ring and a genuinely non-ring near-ring is emphasized as an essential point for future research.

Keywords: graph near-ring; finite near-ring; graph ring; subgraph vector space; symmetric difference; ring sum; IF; transformation near-ring; Boolean ring; digital graph.

1. Introduction

   The interaction between graph theory and algebra has produced many useful structures, including incidence spaces, cycle spaces, cut spaces, matroids, graph algebras, and graph-based transformation semigroups. A particularly simple and powerful observation is that the collection of edge subsets of a finite graph is naturally a vector space over the two-element field IF. If two edge sets are added modulo 2, an edge occurring in both sets disappears, while an edge occurring in exactly one set remains. This is precisely the symmetric difference, commonly called the ring sum of graphs.

   Near-rings generalize rings by requiring only one distributive law, depending on the convention adopted. They occur naturally in transformation theory because addition can be defined pointwise while multiplication is defined by composition. This makes graph-associated vector spaces a natural domain on which finite transformation near-rings can act.

   The aim of this paper is not merely to rename the familiar Boolean ring of subgraphs as a near-ring. Rather, the paper separates two levels of structure. First, the symmetric-difference/intersection construction gives finite Boolean rings, which are automatically near-rings. Second, transformation systems acting on graph

   spaces provide the natural route to finite near-rings that need not be rings. This distinction strengthens the mathematical formulation and identifies a direction for genuinely new research.

   The paper is organized as follows. Section 2 gives basic definitions. Section 3 establishes the subgraph vector- space construction. Section 4 develops graph rings from symmetric difference and intersection. Section 5 gives explicit examples and Cayley tables. Section 6 introduces graph transformation near-rings. Section 7 proves finiteness and structural results. Section 8 discusses applications, and Section 9 gives conclusions and directions for further work.

2. Preliminaries

   1. Graphs and subgraphs

      Let G = (V,E) be a finite simple graph. A subgraph H of G may be represented by its edge set E(H) E (with the relevant incident vertices understood). For algebraic purposes it is convenient to identify a subgraph with its edge subset.

      Definition 2.1. Edge-subset space

      For a finite graph G with m = |E| edges, define IF(G) = {X : X E}. Thus |IF(G)| = 2^m.

      Definition 2.2. Ring sum

      For X,Y E, their ring sum or symmetric difference is X Y = (X\Y) u (Y\X). In binary incidence-vector notation, _{XY} = _X + _Y over IF.

      Definition 2.3. Near-ring

      A right near-ring is an algebraic system (N,+,·) such that (N,+) is a group, (N,·) is a semigroup, and right distributivity (a+b)c = ac+bc holds for all a,b,c E N. Some authors use the opposite distributive convention; throughout this paper the displayed convention is used. If both distributive laws hold and the additive group is abelian, the structure is a ring.

      Definition 2.4. Boolean ring

      A ring R is Boolean if x² = x for every x E R. Every Boolean ring is a near-ring under the definition above.

3. Subgraph Spaces over IF

   Theorem 3.1. Edge-space theorem

   Let G be a finite graph with m edges. Then (IF(G), ) is an abelian group and IF(G) is a vector space over IF of dimension m. In particular, IF(G) = IF^m and |IF(G)| = 2^m.

   Proof. Choose an ordering E = {e,,e_m}. Associate to each X E the binary vector _X = (_X(e),,_X(e_m)). This map is bijective from IF(G) to IF^m. Symmetric difference corresponds to coordinatewise addition modulo 2, so _{XY} = _X + _Y. The empty edge set is the zero vector, and scalar multiplication is 0X = 0 and 1X = X. Hence IF(G) is a vector space isomorphic to IF^m.

   Corollary 3.2

   If G has m edges, then the number of subgraphs represented by edge subsets is 2^m.

   Proof. There are two independent choices for each of the m edges: inclusion or exclusion. Therefore the total number is 2^m.

   1. Cycle space

      The cycle space C(G) is the subspace of IF(G) generated by the edge sets of cycles. If G has n vertices, m edges, and c connected components, then dim C(G) = m n + c. Consequently |C(G)| = 2^(mn+c). This provides a natural family of finite graph vector spaces of powers-of-two cardinality.

      Theorem 3.3. Cycle-space cardinality

      For a finite graph G with n vertices, m edges, and c connected components, the cycle space has 2^(mn+c)

      elements.

      Proof. A spanning forest of G contains nc edges. Each edge outside the spanning forest produces a fundamental cycle. There are m(nc) = mn+c such independent fundamental cycles, which form a basis of the cycle space over IF. Hence the dimension is mn+c and the cardinality is 2^(mn+c).

4. Graph Rings from Symmetric Difference and Intersection

   A first algebraic structure is obtained by defining addition as symmetric difference and multiplication as intersection:

   X + Y = X Y, XY = X Y.

   Theorem 4.1. Boolean graph-ring theorem

   For every finite graph G, R(G) = (IF(G), , ) is a commutative Boolean ring and therefore a finite near-ring.

   Proof. Symmetric difference is associative and commutative, with identity 0 and inverse X itself, because XX = 0 . Intersection is associative and commutative and has 0 as a multiplicative zero. The distributive identity X (YZ) = (XY)(XZ) follows by checking each edge independently. Finally XX = X for every X, so the ring is Boolean. Since every ring satisfies the near-ring axioms, R(G) is a finite near-ring.

   Remark 4.2

   The construction in Theorem 4.1 is not a genuinely non-ring near-ring. It is a Boolean ring. This distinction is important when claiming novelty in a journal paper: the graph-ring construction is a standard algebraic onsequence of set operations, while genuinely non-ring near-rings should arise from transformation or other one-sided distributive constructions.

5. Explicit Finite Examples and Cayley Tables

   1. Order 2

      Let G have one edge e. Write 0 = 0 and 1 = {e}. Then R(G) has two elements.

      	0	1
      0	0	1
      1	1	0

      Table 1. Addition (ring sum) for the order-2 graph ring.

      	0	1
      0	0	0

      1

      0

      1

      Table 2. Multiplication (intersection) for the order-2 graph ring.

   2. Order 4

      Let E = {e,e}. Use the abbreviations 0=0 , a={e}, b={e}, c={e,e}.

      	0	a	b	c
      0	0	a	b	c
      a	a	0	c	b
      b	b	c	0	a
      c	c	b	a	0

      Table 3. Addition table for the order-4 graph ring.

      	0	a	b	c
      0	0	0	0	0
      a	0	a	0	a
      b	0	0	b	b
      c	0	a	b	c

      Table 4. Multiplication table for the order-4 graph ring.

   3. Order 8

      Let E = {e,e,e}. Use 0=0 , a={e}, b={e}, c={e}, d={e,e}, e={e,e}, f={e,e}, g={e,e,e}.

      	0	a	b	c	d	e	f	g
      0	0	a	b	c	d	e	f	g
      a	a	0	d	e	b	c	g	f
      b	b	d	0	f	a	g	c	e
      c	c	e	f	0	g	a	b	d
      d	d	b	a	g	0	f	e	c
      e	e	c	g	a	f	0	d	b
      f	f	g	c	b	e	d	0	a
      g	g	f	e	d	c	b	a	0

      Table 5. Addition table for the order-8 graph ring.

      	0	a	b	c	d	e	f	g
      0	0	0	0	0	0	0	0	0
      a	0	a	0	0	a	0	0	a
      b	0	0	b	0	b	0	b	b
      c	0	0	0	c	0	c	c	c
      d	0	0	0	0	d	0	0	d
      e	0	0	0	0	0	e	0	e
      f	0	0	0	0	0	0	f	f
      g	0	a	b	c	d	e	f	g

      Table 6. Multiplication table for the order-8 graph ring.

   4. Order 16

      Let E = {e,e,e,e}. Then IF(G) has 16 elements and is isomorphic to IF. Listing all 16-by-16 tables is possible but unnecessarily large. The operations are completely determined by bitwise XOR for addition and bitwise AND for intersection. Thus, if a subset is encoded by a four-bit word, then graph ring sum is XOR and multiplication is AND.

      Table 7. Compact Cayley representation for order 16.

      Operation	Binary representation	Example
      Addition	bitwise XOR	1010 0110 = 1100
      Multiplication	bitwise AND	1010 0110 = 0010

      Zero	0000	0
      Identity	1111	{e,e,e,e}

      The compact representation is mathematically equivalent to the full 16-by-16 Cayley tables and is more suitable for computational implementation.

      Proposition 5.5

      For an m-edge graph, encoding each edge subset by an m-bit binary word converts graph ring sum into bitwise XOR and intersection into bitwise AND.

      Proof. Each edge is represented by one bit. Symmetric difference keeps an edge precisely when it occurs in exactly one operand, which is XOR. Intersection keeps an edge precisely when it occurs in both operands, which is AND.

6. Graph Transformation Near-Rings

   To move beyond Boolean graph rings, consider transformations of a graph-associated vector space. Let V_G =

   IF(G) = IF^m. A family N of functions f:V_GV_G can be equipped with pointwise addition and composition: (f+g)(X) = f(X) g(X), (fg)(X) = f(g(X)).

   Definition 6.1. Graph transformation near-ring

   A graph transformation near-ring is a finite near-ring whose elements are transformations of V_G and whose action is interpreted as an operation on graph edge states or subgraphs.

   Theorem 6.2. Finiteness of graph transformation systems

   Let G have m edges. Any near-ring of transformations acting on V_G is finite.

   Proof. Since |V_G|=2^m, the set of all functions V_GV_G has (2^m)^(2^m)=2^(m2^m) elements. A transformation near-ring is a subset of this finite set, hence is finite.

   1. Linear transformation example of order 16

      Take V = IF². Its linear endomorphisms are represented by the 16 matrices A = [[a,b],[c,d]], where a,b,c,dE IF. Addition is matrix addition modulo 2 and multiplication is matrix composition, i.. matrix

      multiplication modulo 2. Therefore End_{IF}(V) has order 16. This is a finite ring and hence a near-ring. The graph interpretation is obtained by identifying the two coordinates with two independent edge-state variables or two basis subgraphs.

   2. Toward genuinely non-ring near-rings

      A genuinely non-ring example requires a transformation family for which only one distributive law is retained. In a transformation near-ring, one can enlarge the class of admissible mappings beyond linear transformations while imposing closure and the chosen one-sided distributive condition. Such structures should be studied as graph-state transformation near-rings rather than as simple Boolean graph rings.

      Research Problem 6.3

      For a fixed graph G, classify finite transformation families N_G Map(IF(G),IF(G)) that are closed under pointwise addition and composition and satisfy exactly one distributive law. Determine conditions under which N_G is a ring, a proper near-ring, or a near-field-like structure.

7. Further Structural Results

   Theorem 7.1. Order of the full graph ring

   If G has m edges, then the Boolean graph ring R(G)=(IF(G),,) has order 2^m.

   Proof. By Theorem 3.1, |IF(G)|=2^m. The operations do not change the underlying set.

   Theorem 7.2. Every element is idempotent

   For every XE IF(G), X²=X in R(G).

   Proof. Multiplication is intersection, so X²=XX=X.

   Theorem 7.3. Graph-ring characteristic

   The graph ring R(G) has characteristic 2.

   Proof. For every X, XX=0 , the additive identity. Thus 2X=0 for every X, and since a nonzero one-edge subset exists when E is nonempty, the characteristic is exactly 2.

   Theorem 7.4. Boolean representation

   For a graph with m edges, R(G) is isomorphic to the direct product of m copies of IF: R(G)

   = IF × IF × ··· × IF (m factors).

   Proof. Map each edge subset to its binary incidence vector. Under symmetric difference and intersection, the coordinates operate as addition and multiplication in IF. Therefore the map is a ring isomorphism.

8. Applications

   1. Digital logic

      The identification of graph ring sum with XOR is immediate. A graph edge can represent a binary wire or switch, and a subgraph represents a complete binary state. Symmetric difference implements toggling/XOR, while intersection implements AND. Hence the order-2^m graph ring provides an algebraic model of m binary switching variables.

   2. Switching networks

      In switching theory, edges may encode switch states. Ring sum models a change in the parity of activation, while graph transformations can model state transitions or switching operations.

   3. Finite automata

      Let V_G be the finite state space of subgraph configurations. A transformation f:V_GV_G can represent a transition. A near-ring of transformations provides an algebraic environment in which several transition operations can be combined and composed.

   4. Coding theory

      The edge space and cycle space are binary vector spaces. Selecting subspaces gives binary linear codes. Graph transformations may then be used to represent encoding, permutation, or state-transition operations.

   5. Cryptography

      Finite binary transformation structures are relevant to cryptographic state transformations. Graph-induced near-rings may provide a framework for studying algebraic properties of binary mappings, although cryptographic security requires additional analysis and should not be inferred from algebraic closure alone.

9. DISCUSSION

   The main conceptual point is that graph ring sum is not merely an informal graph operation: it is exactly vector addition over IF. This makes subgraph families suitable objects for finite algebraic study. The intersection construction yields a Boolean ring, while transformation composition provides a pathway to near-ring structures.

   For a publishable research contribution, the most promising next step is not to claim that the Boolean ring itself is new, but to investigate graph transformation near-rings that are not rings. Potential directions include classification by graph invariants, construction of nonabelian additive examples, ideal structure, zero divisors, automorphism groups, computational enumeration, and applications to digital finite-state systems.

   The order-2, order-4, order-8, and order-16 examples demonstrate the finite nature of the construction. Their binary encodings also make them suitable for computer implementation. In particular, the order-16 example is naturally represented by four-bit words and can be implemented using XOR and AND operations.

   A future paper may define a specific graph multiplication that is not simply intersection, prove one-sided distributivity, and establish that the resulting structure is a proper near-ring. Such a result would provide stronger novelty than the Boolean-ring examples alone.

10. CONCLUSION

Finite graphs naturally generate algebraic structures through their edge subsets. The edge-subset space IF(G) is a vector space over IF, with graph ring sum corresponding to vector addition. This immediately produces finite Boolean graph rings of orders 2^m. Explicit examples of orders 2, 4, 8, and 16 were developed, and their Cayley operations were displayed using symmetric difference and intersection.

Because every ring is a near-ring, these graph rings are finite near-rings, but they are not genuinely non-ring near-rings. To broaden the theory, graph transformation near-rings were introduced using transformations of the graph subspace, pointwise addition, and composition. This provides a natural framework for studying one- sided distributive structures associated with graphs.

The framework has potential applications in digital logic, switching theory, finite automata, coding theory, and graph-based computation. The principal open direction is the construction and classification of proper graph near-rings that do not satisfy both distributive laws. Such structures may provide a fruitful intersection of graph theory, finite algebra, and digital mathematics.

REFERENCES

1. G. Pilz, Near-Rings: The Theory and Its Applications, North-Holland, Amsterdam, 1983.

2. J. D. P. Meldrum, Near-Rings and Their Links with Groups, Pitman, London, 1985.

3. R. Diestel, Graph Theory, 5th ed., Springer, Berlin, 2017.

4. J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2008.

5. C. Godsil and G. Royle, Algebraic Graph Theory, Springer, New York, 2001.

6. N. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge University Press, Cambridge, 1993.

7. G. L. Peterson, On the structure of an endomorphism near-ring, Proceedings of the Edinburgh Mathematical Society, 32 (1989), 223229.

8. H. E. Heatherly and J. D. P. Meldrum, Finiteness conditions for near-rings, Canadian Mathematical Bulletin.

9. S. Ligh and J. J. Malone Jr., Zero divisors and finite near-rings, Journal of the Australian Mathematical Society.

10. J. S. Golan, Semirings and Their Applications, Kluwer Academic Publishers, Dordrecht, 1999.

11. B. Bollobás, Modern Graph Theory, Springer, New York, 1998.

12. D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2001.

Appendix A. Complete Order-4 Cayley Tables

The order-4 example can also be interpreted as the Boolean agebra on two edge variables. Its four elements are 00, 10, 01, 11. Addition is XOR and multiplication is AND.

Appendix B. Binary Encoding of the Order-8 Example

Under this encoding, symmetric difference is bitwise XOR and intersection is bitwise AND. For example, 110 XOR 011 = 101, while 110 AND 011 = 010.