Prime Graphs with Almost True Twin Vertices

Aymen Ben Amira () and Moncef Bouaziz
Additional contact information
Aymen Ben Amira: Department of Mathematics, College of Sciences, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia
Moncef Bouaziz: Department of Mathematics, College of Sciences, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia

Mathematics, 2025, vol. 13, issue 21, 1-25

Abstract: A graph G consists of a possibly infinite set V ( G ) of vertices with a collection E ( G ) of unordered pairs of distinct vertices, called the set of edges of G . Such a graph is denoted by ( V ( G ) , E ( G ) ) . Two distinct vertices u and v of a graph G are adjacent if { u , v } ∈ E ( G ) . Let G be a graph. A subset M of V ( G ) is a module of G if every vertex outside M is adjacent to all or none of the vertices in M . The graph G is prime if it has at least four vertices, and its only modules are ∅, the single-vertex sets, and V ( G ) . Given two adjacent vertices u and v of G , v is a negative almost true twin of u in G if there is a vertex x v in V ( G ) ∖ { u } non-adjacent to u such that the pair { u , v } is a module of the graph ( V ( G ) , E ( G ) ∪ { { u , x v } } ) . In this paper, we study graphs with a negative almost true twin for a given vertex, and we give some applications. Firstly, we characterize these graphs by a special decomposition, and we specify the prime graphs among them. Secondly, we give three applications, giving methods for extending graphs to prime graphs. Finally, we study the prime induced subgraphs of the prime graphs with at least two negative almost true twins for a given vertex.

Keywords: module; prime; modular decomposition; negative almost true twin (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/21/3466/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/21/3466/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:21:p:3466-:d:1783527

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().