On the number of spanning trees of K-n(m) +/- G graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Discrete Mathematics & Theoretical Computer Science
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Mathematics and Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
The K-n-complement of a graph G, denoted by K-n - G, is defined as the graph obtained from the complete graph Kn by removing a set of edges that span G; if G has n vertices, then K n - G coincides with the complement G of the graph G. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form K-n(m) +/- G, where K-n(m) is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of K m n; the graph K-n(m) + G (resp. K-n(m) - G) is obtained from K-n(m) by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from K m n by adding and removing edges of multigraphs spanned by sets of edges of the graph K-n(m). We also prove closed formulas for the number of spanning tree of graphs of the form K-n(m) +/- G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees.
Περιγραφή
Λέξεις-κλειδιά
kirchhoff matrix tree theorem, complement spanning tree matrix, spanning trees, k-n-complements, multigraphs, chebyshev polynomials, formulas, circulant
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000202967200003
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών