Mathematics – Combinatorics
Scientific paper
2007-12-19
Mathematics
Combinatorics
17 pages, 2 figures
Scientific paper
We look for graph polynomials which satisfy recurrence relations on three kinds of edge elimination: edge deletion, edge contraction and deletion of edges together with their end points. Like in the case of deletion and contraction only (W. Tutte, 1954), it turns out that there is a most general polynomial satisfying such recurrence relations, which we call $\xi(G,x,y,z)$. We show that the new polynomial simultaneously generalizes the Tutte polynomial, the matching polynomial, and the recent generalization of the chromatic polynomial proposed by K.Dohmen, A.P\"{o}nitz and P.Tittman (2003), including also the independent set polynomial of I. Gutman and F. Harary, (1983) and the vertex-cover polynomial of F,M. Dong, M.D. Hendy, K.T. Teo and C.H.C. Little (2002). We establish two definitions of the new polynomial: first, the most general confluent recursive definition, and then an explicit one, using a set expansion formula, and prove their identity. We further expand this result to edge-labeled graphs as was done for the Tutte polynomial by T. Zaslavsky (1992) and B. Bollob\'as and O. Riordan (1999). The edge labeled polynomial $\xi_{lab}(G,x,y,z, \bar{t})$ also generalizes the chain polynomial of R.C. Read and E.G. Whitehead Jr. (1999). Finally, we discuss the complexity of computing $\xi(G,x,y,z)$.
Averbouch Ilia
Godlin Benny
Makowsky Johann A.
No associations
LandOfFree
A most general edge elimination graph polynomial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A most general edge elimination graph polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A most general edge elimination graph polynomial will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-146267