{
  "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.",
  "abstract_shown": true,
  "affiliations": [
    "Department of Mathematics, College of Sciences, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia"
  ],
  "article_type": null,
  "arxiv": null,
  "author_total": 1,
  "authors": [
    {
      "affs": [
        0
      ],
      "name": "Imed Boudabbous"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/f2hy5rffh641j.bib",
  "cited_by": 0,
  "doi": "10.3390/math14203747",
  "fulltext_url": null,
  "id": "f2hy5rffh641j",
  "issns": [
    "2227-7390"
  ],
  "landing_url": "https://www.mdpi.com/2227-7390/14/20/3747",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7222258361",
  "pdf_url": null,
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-15",
  "publisher": "MDPI AG",
  "ris": "https://research.draconitic.com/paper/f2hy5rffh641j.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:29Z",
      "native_id": "10.3390/math14203747",
      "source": "crossref",
      "url": "https://www.mdpi.com/2227-7390/14/20/3747"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "issn:2227-7390",
      "subfield": "general"
    }
  ],
  "title": "On the Number of Non-Critical Vertices in Prime Graphs",
  "title_text": "On the Number of Non-Critical Vertices in Prime Graphs",
  "type": "peer-reviewed",
  "updated_at": "2026-10-30T12:18:29Z",
  "url": "https://research.draconitic.com/paper/f2hy5rffh641j",
  "venue": "Mathematics",
  "versions": []
}