✦ LIBER ✦

The matching polynomial of a regular graph

✍ Scribed by Robert A. Beezer; E.J. Farrell

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 588 KB
Volume: 137
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0125-n

No coin nor oath required. For personal study only.

✦ Synopsis

The matching polynomial of a graph has coefficients that give the number ofmatchings in the graph. For a regular graph, we show it is possible to recover the order, degree, girth and number of minimal cycles from the matching polynomial. If a graph is characterized by its matching polynomial, then it is called matching unique. Here we establish the matching uniqueness of many specific regular graphs; each of these graphs is either a cage, or a graph whose components are isomorphic to Moore graphs. Our main tool in establishing the matching uniqueness of these graphs is the ability to count certain subgraphs of a regular graph.

📜 SIMILAR VOLUMES

Computational algorithms for matching po

Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs

✍ Haruo Hosoya; K. Balasubramanian 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 736 KB

Computational algorithms are described which provide for constructing the set of associated edgeweighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or pur

On the Multiplicities of the Primitive I

On the Multiplicities of the Primitive Idempotents of a Q-Polynomial Distance-regular Graph

✍ Arlene A Pascasio 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 154 KB

and Terwilliger recently introduced the notion of a tridiagonal pair. We apply their results to distance-regular graphs and obtain the following theorem. THEOREM. Let denote a distance-regular graph with diameter D ≥ 3. Suppose is Q-polynomial with respect to the ordering E 0 , E 1 , . . . , E D of

The Wiener polynomial of a graph

✍ Bruce E. Sagan; Yeong-Nan Yeh; Ping Zhang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 674 KB

The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog of the Wiener index. We study some of the elementary properties of this polynomial and compute it for some

Bipartite Q-Polynomial Quotients of Anti

Bipartite Q-Polynomial Quotients of Antipodal Distance-Regular Graphs

✍ John S. Caughman IV 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 91 KB

Let 1 denote a bipartite Q-polynomial distance-regular graph with diameter D 4. We show that 1 is the quotient of an antipodal distance-regular graph if and only if one of the following holds. (i) 1 is a cycle of even length. (ii) 1 is the quotient of the 2D-cube. 1999 Academic Press \* , ..., %\

Spectra of Regular Graphs and Hypergraph

Spectra of Regular Graphs and Hypergraphs and Orthogonal Polynomials

✍ Wen-Ch'ing Winnie Li; Patrick Solé 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 339 KB

Circumference of a regular graph

✍ Min Aung 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB