On highly irregular graphs

• Main Author: King, Tiffany Kai T.
• Format: text
• Language: English
• Published: Animo Repository 2006
• Subjects: Graph theory; Matrices; Combinatorial analysis
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/17423
• Institution: De La Salle University

This thesis is an exposition of the results discussed in two articles, namely, Highly Irregular graphs by Yousef Alavi, Gary Cahrtland, et al., published in Journal of Graph Theory, Volume II, No. 2, in 1987, and Highly Irregular Multitrees by Yousef Alavi, Don R. Lick, and Terry A. McKeet which appeared in graph Theory, Combinatorics, Algorithms and Applications in 1991. The thesis defines a highly irregular graph and discusses elementary properties of highly irregular graphs. It proves that every graph of order n 2 is an induced subgraph of a highly irregular graph. It also shows that the order n of a highly irregular tree with maximum degree d is at least 2. Furthermore, it proved that a multitree of maximum degree d and strength two is the unique highly irregular multitree of minimum possible order and minimum possible size.