On the Number of Non-Critical Vertices in Prime Graphs
- 1Department of Mathematics, College of Sciences, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia
Abstract
Let G=(V,E) be a finite simple graph. A module of G is a subset M⊆V such that every vertex in V∖M is adjacent either to all vertices of M or to none of them. The sets ∅, V, and the singletons of V are called the trivial modules of G. The graph G is decomposable if it has a non-trivial module; otherwise, it is indecomposable The graph G is prime if it is indecomposable and has at least four vertices. A vertex x of a prime graph G is critical if the induced subgraph G−x is decomposable. We give a complete answer to the following existence problem: for which integers n and k does there exist a prime graph on n vertices with exactly k non-critical vertices? Our first main result shows that, for all integers n≥8 and 2≤k≤n, such a graph exists and can be chosen to be triangle-free; for k=1, a triangle-free example exists if and only if n is even. Our second main result states that, for all integers n≥6 and 1≤k≤n, such a graph exists. Both bounds n≥8 and n≥6 are tight. Together with the classical result of Schmerl and Trotter for k=0, this settles the existence problem. All proofs are constructive: the required graphs are built explicitly by means of modular decomposition.
Related
- Anti-Ramsey Number for Suspension of Edge-Critical Graphs
- The minimum number of vertices of a triangulation of ℝℙ5
- Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
- Saturation numbers for joins with graphs containing isolated vertices
- Near-optimal Turán densities of r-graphs on r+1 vertices
BibTeX
@article{boudabbous2026number,
title = {{On the Number of Non-Critical Vertices in Prime Graphs}},
author = {Imed Boudabbous},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14203747},
url = {https://www.mdpi.com/2227-7390/14/20/3747},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - On the Number of Non-Critical Vertices in Prime Graphs
AU - Imed Boudabbous
PY - 2026
DA - 2026/10/15
JO - Mathematics
DO - 10.3390/math14203747
UR - https://www.mdpi.com/2227-7390/14/20/3747
AB - Let G=(V,E) be a finite simple graph. A module of G is a subset M⊆V such that every vertex in V∖M is adjacent either to all vertices of M or to none of them. The sets ∅, V, and the singletons of V are called the trivial modules of G. The graph G is decomposable if it has a non-trivial module; otherwise, it is indecomposable The graph G is prime if it is indecomposable and has at least four vertices. A vertex x of a prime graph G is critical if the induced subgraph G−x is decomposable. We give a complete answer to the following existence problem: for which integers n and k does there exist a prime graph on n vertices with exactly k non-critical vertices? Our first main result shows that, for all integers n≥8 and 2≤k≤n, such a graph exists and can be chosen to be triangle-free; for k=1, a triangle-free example exists if and only if n is even. Our second main result states that, for all integers n≥6 and 1≤k≤n, such a graph exists. Both bounds n≥8 and n≥6 are tight. Together with the classical result of Schmerl and Trotter for k=0, this settles the existence problem. All proofs are constructive: the required graphs are built explicitly by means of modular decomposition.
SN - 2227-7390
ER -