# 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
• Moncef Bouaziz King Saud University

## 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.

2023-10-30

## How to Cite

Alorini, A., Ben Amira, A., Alzohairi, M., & Bouaziz, M. (2023). Prime Graph Generation through Single Edge Addition: Characterizing a Class of Graphs. European Journal of Pure and Applied Mathematics, 16(4), 2786–2797. https://doi.org/10.29020/nybg.ejpam.v16i4.4829

## Section

Nonlinear Analysis