Some constructions of 3-minimal graphs with cycles

Issue Date

6-2020

Abstract

Prime graphs with triangles – namely (a) Pk ∪ {i(i + 2)} with k ≥ 5 and 2 ≤ i ≤ k − 3, (b) Qk with k ≥ 5, and (c) Sk,m,n with an additional edge to form a triangle – were constructed and shown 3-minimal for some vertex-subsets. If G has a triangle and is 3-minimal for a nonstable subset X of V(G), it was shown that G is isomorphic to either P5 ∪ {22} ≅ Q5 or Pk ∪ {(k − 3)(k − 21)}. If G has a triangle and is 3-minimal for a stable subset X of V(G), with A ⊆ V(G) such that G[A] is P5 ∪ {22} ≅ Q5, then either X ∩ A = ∅ or X ∩ A ≠ ∅. If X ∩ A = ∅, it was shown that G is isomorphic to one of the forms of Sk,m,n with an additional edge to form a triangle. If X ∩ A ≠ ∅, it was shown that G is isomorphic to one of the following: (a) one of the forms of Sk,m,n with an additional edge to form a triangle; (b) Pk ∪ {i(i + 2)} with k ≥ 6 and 2 ≤ i ≤ k − 3; and (c) Qk with k ≥ 5.

Source or Periodical Title

Philippine Journal of Science

ISSN

0031-7683

Volume

149

Issue

2

Page

269-277

Document Type

Article

Physical Description

figures; references

Language

English

Subject

Graphs, Indecomposable, K-minimal, Minimal, Prime

Identifier

10.56899/149.02.03.

Digital Copy

yes

Link to Full Text

Share

COinS