Philippine Journal of Science
149 (2): 269-277, June 2020
ISSN 0031 – 7683
Date Received: 15 Oct 2019

 

Some Constructions of 3-minimal Graphs with Cycles

 

Wielson M. Factolerin* and Jean O. Loyola

 

Institute of Mathematical Sciences and Physics (IMSP), College of Arts and Sciences University of the Philippines Los Banos (UPLB), College, Laguna 4031 Philippines

 

*Corresponding author: wmfactolerin@up.edu.ph
AMS Subject Classifications: 97K30

 

[Download]
Factolerin W, Loyola J. 2020. Some Constructions of 3-minimal Graphs with
Cycles. Philipp J Sci 149(2): 269–277. https://doi.org/10.56899/149.02.03

 

ABSTRACT

Prime graphs with triangles namely (a) P k ∪ {i(i + 2)} with k >= 5 and 2 < i < k – 3 (b) Qk with k > 5 and (c) S k ,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 P 5 ∪ {24} ≅ Q 5 or Pk ∪ {(k – 3)(k – 1)} , 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 ∪ {24} ≅ Q5 , then either X ∩ A= ∅ or X ∩ A ≠ ∅ . If X ∩ A = ∅ , it was shown that G is isomorphic to one of the forms of S k, 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 S k, 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.