Prime Graph Generation through Single Edge Addition: Characterizing a Class of Graphs

Authors

  • Ayesha Alorini Imam Mohammad Ibn Saud University
  • Aymen Ben Amira King Saud University
  • Mohammad Alzohairi
  • Moncef Bouaziz King Saud University

DOI:

https://doi.org/10.29020/nybg.ejpam.v16i4.4829

Keywords:

module, prime, decomposable, prime frame, isomorphism

Abstract

A graph G consists of a finite set V (G) of vertices with a collection E(G) of unordered pairs of distinct vertices called edge set of G. Let G be a graph. A set M of vertices is a module of G if, for vertices x and y in M and each vertex z outside M, {z, x} ∈ E(G) ⇐⇒ {z, y} ∈ E(G). Thus, a module of G is a set M of vertices indistinguishable by the vertices outside M. The empty set, the singleton sets and the full set of vertices represent the trivial modules. A graph is indecomposable if all its modules are trivial, otherwise it is decomposable. Indecomposable graphs with at least four vertices are prime graphs. The introduction and the study of the construction of prime graphs obtained from a given decomposable graph by adding one edge constitue the central points of this paper.

Downloads

Published

2023-10-30

Issue

Section

Nonlinear Analysis

How to Cite

Prime Graph Generation through Single Edge Addition: Characterizing a Class of Graphs. (2023). European Journal of Pure and Applied Mathematics, 16(4), 2786-2797. https://doi.org/10.29020/nybg.ejpam.v16i4.4829