Description of the minimal prime extension pairs of the 3-vertex graphs

Journal Article

2022

Published in: صفحة

Abstract: In a graph G, a module is a vertex subset M such that every vertex outside M is either adjacent to all or none of M. A graph G with at least three vertices is called prime if the empty set, the singleton sets, and the full set of vertices are the only modules in G, otherwise G is decomposable. Up to isomorphism, all the 3-vertex graphs K3, K3, P3, and P3 are decomposable. A prime graph G is k-minimal if there is some k-element vertex subset A such that each proper induced subgraph of G containing A is decomposable. In 1998, A. Cournier and P. Ille described the 1-minimal and 2-minimal graphs. Then in 2014, M. Alzohairi and Y. Boudabbous described the 3-minimal triangle-free graphs. In this paper, we describe all 3-minimal graphs. To do so, we introduce the following notion. Given a decomposable graph H, a minimal prime extension pair of H (or minimal prime H-extension pair) is an ordered pair (G, A), where G is a prime graph and A is a vertex subset of G such that G[A] is isomorphic to H and no proper induced subgraph of G containing A is prime. The order of such a pair (G, A) is that of G. Two minimal prime H-extension pairs (G, A) and (G', A') are isomorphic if there is an isomorphism f from G onto G' such that f (A) = A'. For each element H of {K3, K3, P3, P3}, we describe up to isomorphism the minimal prime H-extension pairs and we give, for each integer n = 4, the number of nonisomorphic such pairs with order n when H ∈ {P3, P3}.

• Publication Work Type: دكتوراه
• Publisher Name: Old City Publishing
• Publishing City: USA
• Volume Number: 39
• Issue Number: 2-4
• Magazine \ Newspaper: https://web.s.ebscohost.com/abstract?site=ehost&scope=site&jrnl=15423980&AN=158742108&h=TY2eqTRbyG78SooquVflnvWUrd7KJOtSRn63wtlu0IpT7Kf95ReM4xu9%2bBGxQZ8Gf67XbbCIO%2fF3AA80XdrUGg%3d%3d&crl=c&resultLocal=ErrCrlNoResults&resultNs=Ehost&crlhashurl=login.aspx
• Pages: 291 إلى 340