On biconnected graphs

• Main Author: Gonzaga, Alex C.
• Format: text
• Language: English
• Published: Animo Repository 1995
• Subjects: Graph theory; Trees (Graph theory); Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1662; https://animorepository.dlsu.edu.ph/context/etd_masteral/article/8500/viewcontent/TG02389_F_Redacted.pdf
• Institution: De La Salle University

A graph G is said to be biconnected if G and its complement G prime are connected.This study, presents and proves necessary and sufficient conditions for biconnectedness of graphs, in general, and trees, in particular. It also introduces and investigates properties of a new class of graphs known as the maximal biconnected graphs. Furthermore, the study states and proves a theorem on the greatest lower bound and least upper bound of independence, dominance, chromatic and connectivity numbers of biconnected graphs of order n equal to or greater than 4. A simple formula that also specifies characteristic number - nullity - is applied in proving theorems concerning biconnected graphs G such that both G and G prime satisfy specified properties. Also, it states and proves properties of some graph operations on biconnected graphs such as graphing, sum, cartesian product and conjunction. Finally, a theorem on the diameter of biconnected graph is stated and proved.