On the number of spanning trees of multi-star related graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Rondogiannis, P.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Information Processing Letters
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper we compute the number of spanning trees of a specific family of graphs using techniques from linear algebra and matrix theory. More specifically, we consider the graphs that result from a complete graph K-n after removing a set of edges that spans a multi-star graph K-m(a(1), a(2),..., a(m)). We derive closed formulas for the number of spanning trees in the cases of double-star (m = 2), triple-star (m = 3), and quadruple-star (m = 4). Moreover for each case we prove that the graphs with the maximum number of spanning trees are exactly those that result when all the ais are equal. (C) 1998 Elsevier Science B.V.
Περιγραφή
Λέξεις-κλειδιά
spanning trees, multi-star graphs, complement spanning tree matrix theorem, combinatorial problems, interconnection networks
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής