𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A solution to Gutman's problem on the characteristic polynomial of a bipartite graph

✍ Scribed by Xueliang Li; Heping Zhang

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
209 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this short paper, we present a solution to Gutman's problem on the characteristic polynomial of a bipartite graph (Research Problem 134, Discrete Math. 88 (1991)). In [2] I. Gutman proposed a research problem which is stated as follows. The matchings polynomial of a graph G is defined by cl(G,x) = c (-l)km(G,k)x"-2k, k=O where n is the number of vertices of G and m(G, k) is the number of k-matchings in G. By convention, m(G,O) = 1. Define cc(G, x, y) = 1 (-l)km(G, k)x"-2kyk. k=O It is not difficult to determine that %G, x, Y) a' = -WEE(G) c a(G -u -u,x,Y), (*I Let ~(G,x) denote the characteristic polynomial of G. If G is a bipartite graph, $(G,x) can be written as $(G,x) = c (-l)kb(G,k)~"-2k k=O

πŸ“œ SIMILAR VOLUMES

Comments on the characteristic polynomia
Comments on the characteristic polynomial of a graph
✍ K. Balasubramanian πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 655 KB

Several unique advantages of the Le Verrier-Fadeev-Frame method for the characteristic polynomials of graphs over the method proposed by Zivkovic recently based on the Givens-Householder method are described. It is shown that the Givens-Householder method proposed by Zivkovic, by itself fails for di

On the evaluation of the characteristic
On the evaluation of the characteristic polynomial of a chemical graph
✍ Tomislav P. Ε½ivkoviΔ‡ πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 583 KB

## Abstract The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the o

On the bipartite independence number of
On the bipartite independence number of a balanced bipartite graph
✍ Odile Favaron; Pedro Mago; Oscar Ordaz πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 603 KB

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63. The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 b

On the number of maximal bipartite subgr
On the number of maximal bipartite subgraphs of a graph
✍ Jesper Makholm Byskov; Bolette AmmitzbΓΈll Madsen; Bjarke Skjernaa πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 72 KB πŸ‘ 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ΒΌ O(1:8613 n ) and give an algorithm that finds all maximal