Some Constructions of 3-minimal Graphs with Cycles. - Faetolerin, Wielson M.; Loyola, Jean O.
Prime graphs with triangles ? namely (a) P_k∪{i(i+2)} with k≥5 and 2≤i≤k-3, (b) Q_k 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 P_k∪{(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 P_5∪{24}≅Q_5, 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) P_k∪{i(i+2)} with k≥6 and 2≤i≤k-3; and (c) Q_k with k≥5.
Keywords: Science -- Periodicals; Graphs; Incomposable; Minimal; Prime; K-minimal.