TAILIEUCHUNG - Defect polynomials and Tutte polynomials of some asymmetric graphs
We then express these Tutte polynomials as generating functions and decode some valuable information about the asymmetric complete flower graph and asymmetric incomplete flower graph. | Turk J Math (2015) 39: 706 – 718 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article Defect polynomials and Tutte polynomials of some asymmetric graphs 1 Eunice MPHAKO-BANDA1 , Toufik MANSOUR2,∗ School of Mathematics, University of the Witwatersrand, Johannesburg, South Africa 2 Department of Mathematics, University of Haifa, Haifa, Israel Received: • Accepted/Published Online: • Printed: Abstract: We give explicit expressions of the Tutte polynomial of asymmetric complete flower graph and asymmetric incomplete flower graph. We then express these Tutte polynomials as generating functions and decode some valuable information about the asymmetric complete flower graph and asymmetric incomplete flower graph. Furthermore, we convert the Tutte polynomials into coboundary polynomials and give explicit expressions of the k -defect polynomials of these structures. Finally, we conclude that nonisomorphic graphs in this class have the same Tutte polynomials, the same chromatic polynomials, and the same defect polynomials. Key words: Tutte polynomial, cycle graph, flower graph, coboundary polynomials, k -defect polynomials 1. Introduction There are several polynomials associated with a graph G ; we refer the reader to [4] for a detailed background. Polynomials play an important role in the study of graphs as they encode various information about a graph. Chromatic polynomials of graphs are sometimes easy to compute. However, Tutte polynomials of such graphs seem harder to find, and if known they are complicated. For example, the chromatic polynomial of Kn is ∏n−1 λ i=1 (λ − i), but the Tutte polynomial of the same structure as described by Tutte [10] and Welsh [11] is complicated. There are several methods that are used to compute the Tutte polynomial of a graph; just to sample a few methods, we refer to [1, 6]. The coboundary polynomial B(G; λ, S) of a .
đang nạp các trang xem trước
