The number of spanning trees in K-n-Complements of quasi-threshold graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Springer Verlag (Germany)
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Graphs and Combinatorics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper we examine the classes of graphs whose K-n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K-n, the K-n-complement of H is the graph K-n-H which is obtained from K-n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K-n-H admitting formulas for the number of their spanning trees.
Περιγραφή
Λέξεις-κλειδιά
spanning trees, complement spanning-tree matrix theorem, trees, quasi-threshold graphs, combinatorial problems, networks
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000224535500008
http://www.springerlink.com/content/4amf1kdbjv6gxp7y/fulltext.pdf
http://www.springerlink.com/content/4amf1kdbjv6gxp7y/fulltext.pdf
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών