A limit characterization for the number of spanning trees of graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Nomikos, C.
Rondogiannis, P.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Information Processing Letters
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G(n)} be a sequence of graphs G(0), G(1), G(2),... that belong to a particular class. We consider graphs of the form K-n - G(n) that result from the complete graph K-n after removing a set of edges that span G(n). We study the spanning tree behaviour of the sequence {K-n - G(n)} when n --> infinity and the number of edges of G(n) scales according to n. More specifically, we define the spanning tree indicator alpha({G(n)}), a quantity that characterizes the spanning tree behaviour of {K-n - G(n)}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges). (C) 2004 Elsevier B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
graphs, spanning trees, combinatorial problems
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής