Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T14:02:34.142Z Has data issue: false hasContentIssue false
  • English
  • Français

Distance Hereditary Graphs and the Interlace Polynomial

Published online by Cambridge University Press:  01 November 2007

JOANNA A. ELLIS-MONAGHAN  and
IRASEMA SARMIENTO
JOANNA A. ELLIS-MONAGHAN
Affiliation:
Department of Mathematics, Saint Michael's College, 1 Winooski Park, Colchester, VT 05439, USA (e-mail: [email protected]
IRASEMA SARMIENTO
Affiliation:
Dipartimento di Matematica, Universitàdi Roma ‘Tor Vergata’, Via della Ricerca Scientifica, I-00133, Rome, Italy (e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollobás and Sorkin in [3] as evolving from questions of DNA sequencing, and extended to a two-variable interlace polynomial by the same authors in [5], evokes many open questions. These include relations between the interlace polynomial and the Tutte polynomial and the computational complexity of the vertex-nullity interlace polynomial. Here, using the medial graph of a planar graph, we relate the one-variable vertex-nullity interlace polynomial to the classical Tutte polynomial when x=y, and conclude that, like the Tutte polynomial, it is in general #P-hard to compute. We also show a relation between the two-variable interlace polynomial and the topological Tutte polynomial of Bollobás and Riordan in [13].

We define the γ invariant as the coefficient of x1 in the vertex-nullity interlace polynomial, analogously to the β invariant, which is the coefficientof x1 in the Tutte polynomial. We then turn to distance hereditary graphs, characterized by Bandelt and Mulder in [9] as being constructed by a sequence ofadding pendant and twin vertices, and show that graphs in this class have γ invariant of 2n+1 when n true twins are added intheir construction. We furthermore show that bipartite distance hereditary graphs are exactly the class of graphs with γ invariant 2, just as the series-parallel graphs are exactly the class of graphs with β invariant 1. In addition, we show that a bipartite distance hereditary graph arises precisely as the circle graph of an Euler circuitin the oriented medial graph of a series-parallel graph. From this we conclude that the vertex-nullity interlace polynomial is polynomial time to compute for bipartite distancehereditary graphs, just as the Tutte polynomial is polynomial time to compute for series-parallel graphs.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 6 , November 2007 , pp. 947 - 973
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aigner, M. and van der Holst, H. (2004) Interlace polynomials. Linear Algebra Appl. 377 11–30.CrossRefGoogle Scholar
[2]Arratia, R., Bollobás, B., Coppersmith, D. and Sorkin, G. (2000) Euler circuits and DNA sequencing by hybridization. Discrete Appl. Math. (special issue on combinatorial molecular biology) 104 63–96.CrossRefGoogle Scholar
[3]Arratia, R., Bollobás, B. and Sorkin, G. (2000) The interlace polynomial: A new graph polynomial. In Proc. 11th Annual ACM–SIAM Symposium on Discrete Algorithms: San Francisco 2000, pp. 237–245.Google Scholar
[4]Arratia, R., Bollobás, B. and Sorkin, G. (2004) The interlace polynomial of a graph. J. Combin. Theory Ser. B 92 199–233.CrossRefGoogle Scholar
[5]Arratia, R., Bollobás, B. and Sorkin, G. (2004) A two-variable interlace polynomial. Combinatorica 24 567–584.CrossRefGoogle Scholar
[6]Ausiello, G., D'Atri, A. and Moscarini, M. (1986) Chordality properties on graphs and minimal conceptual connections in semantic data models. J. Comput. Syst. Sci. 33 179–202.CrossRefGoogle Scholar
[7]Balister, P. N., Bollobás, B., Cutler, J. and Pebody, L. (2002) The interlace polynomial of graphs at -1. Europ. J. Combin. 23 761–767.CrossRefGoogle Scholar
[8]Balister, P. N., Bollobás, B., Riordan, O. M. and Scott, A. D. (2001) Alternating knot diagrams, Euler circuits and the interlace polynomial. Europ. J. Combin. 22 1–4.CrossRefGoogle Scholar
[9]Bandelt, H. J. and Mulder, H. M. (1986) Distance-hereditary graphs. J. Combin. Theory Ser. B 41 182–208.CrossRefGoogle Scholar
[10]Benashki, J., Martin, R., Moore, J. and Traldi, L. (1995) On the β-invariant for graphs. Congr. Numer. 109 211–221.Google Scholar
[11]Bollobás, B. (1998) Modern Graph Theory. Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[12]Bollobás, B. (2002) Evaluations of the circuit partition polynomial. J. Combin. Theory Ser. B 85 261–268.CrossRefGoogle Scholar
[13]Bollobás, B. and Riordan, O. (2001) A polynomial invariant of graphs on orientable surfaces. Proc. London Math. Soc. (3) 83 513–531.CrossRefGoogle Scholar
[14]Bollobás, B. and Riordan, O. (2002) A polynomial of graphs on surfaces. Math. Ann. 323 81–96.CrossRefGoogle Scholar
[15]Bouchet, A. (1986) Characterizing and recognizing circle graphs. In Graph Theory: Dubrovnik 1985, pp. 57–69Google Scholar
[16]Bouchet, A. (1987) Isotropic systems. Europ. J. Combin. 8 231–244.CrossRefGoogle Scholar
[17]Bouchet, A. (1987) Reducing prime graphs and recognizing circle graphs. Combinatorica 7 243–254.CrossRefGoogle Scholar
[18]Bouchet, A. (1987) Unimodularity and circle graphs. Discrete Math. 66 203–208.CrossRefGoogle Scholar
[19]Bouchet, A. (1988) Graphic presentations of isotropic systems. J. Combin. Theory Ser. B 45 58–76.CrossRefGoogle Scholar
[20]Bouchet, A. (1989) Connectivity of isotropic systems. In Combinatorial Mathematics: Proc. 3rd International Conference, New York 1985, Vol. 555 of Ann. NY Acad. Sci., pp. 81–93.Google Scholar
[21]Bouchet, A. (1991) Tutte–Martin polynomials and orienting vectors of isotropic systems. Graphs Combin. 7 235–252.CrossRefGoogle Scholar
[22]Bouchet, A. (1993) Compatible Euler tours and supplementary Eulerian vectors. Europ. J. Combin. 14 513–520.CrossRefGoogle Scholar
[23]Bouchet, A. (1994) Circle graph obstructions. J. Combin. Theory Ser. B 60 107–144.CrossRefGoogle Scholar
[24]Bouchet, A. (2001) Multimatroids III: Tightness and fundamental graphs. In Combinatorial Geometries: Luming 1999. Europ. J. Combin. 22 657–677.Google Scholar
[25]Bouchet, A. (2005) Graph polynomials derived from Tutte–Martin polynomials. Discrete Math. 302 32–38.CrossRefGoogle Scholar
[26]Bouchet, A. and Ghier, L. (1996) Connectivity and β invariants of isotropic systems and 4-regular graphs. Discrete Math. 161 25–44.CrossRefGoogle Scholar
[27]Brandstädt, A., Le, V. B. and Spinrad, J. P. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA.CrossRefGoogle Scholar
[28]Brylawski, T. (1971) A combinatorial model for series-parallel networks. Trans. Amer. Math. Soc. 154 1–22.CrossRefGoogle Scholar
[29]Brylawski, T. (1980) The Tutte polynomial. In Proc. 3rd International Mathematical Summer Centre, pp. 125–275.Google Scholar
[30]Brylawski, T. and Oxley, J. (1992) The Tutte polynomial and its applications. In Matroid Applications, Vol. 40 of Encyclopedia Math. Appl., Cambridge University Press, pp. 123–225.CrossRefGoogle Scholar
[31]Burlet, M. and Uhry, J. P. (1982) Parity graphs. Ann. Discrete Math. 16 1–26.Google Scholar
[32]Cicerone, S. and Di Stefano, G. (1999) Graph classes between parity and distance-hereditary graphs. In Proc. Conference on Optimal Discrete Structures and Algorithms: ODSA '97, Rostock. Discrete Appl. Math. 95 197–216.Google Scholar
[33]Cicerone, S. and Di Stefano, G.(1999) On the extension of bipartite to parity graphs. In Proc. Conference on Optimal Discrete Structures and Algorithms: ODSA '97, Rostock. Discrete Appl. Math. 95 181–195.Google Scholar
[34]Crapo, H. H. (1967) A higher invariant for matroids. J. Combin. Theory 2 406–417.CrossRefGoogle Scholar
[35]Czemerinski, H., Durán, G. and Gravano, A. (2002) Bouchet graphs: A generalization of circle graphs. Congr. Numer. 155 95–108.Google Scholar
[36]Duffin, R. J. (1965) Topology of series-parallel networks. J. Math. Anal. Appl. 10 303–318.CrossRefGoogle Scholar
[37]Durán, G. (2003) Some new results on circle graphs. In Latin-American Workshop on Cliques in Graphs: Rio de Janeiro 2002. Mat. Contemp. 25 91–106.Google Scholar
[38]Ellis-Monaghan, J. A. (1998) New results for the Martin polynomial. J. Combin. Theory Ser. B 74 326–352.CrossRefGoogle Scholar
[39]Ellis-Monaghan, J. A. (2004) Exploring the Tutte–Martin connection. Discrete Math. 281 173–187.CrossRefGoogle Scholar
[40]Ellis-Monaghan, J. A. (2004) Identities for circuit partition polynomials, with applications to the Tutte polynomial. Adv. Appl. Math. 32 188–197.CrossRefGoogle Scholar
[41]Ellis-Monaghan, J. A. and Sarmiento, I. (2002) Generalized transition polynomials. Congr. Numer. 155 57–69.Google Scholar
[42]de Fraysseix, H. (1984) A characterization of circle graphs. Europ. J. Combin. 5 223–238.CrossRefGoogle Scholar
[43]Gasse, E. (1997) A proof of a circle graph characterization. Discrete Math. 173 277–283.CrossRefGoogle Scholar
[44]Howorka, E. (1977) A characterization of distance-hereditary graphs. Quart. J. Math. Oxford Ser. 2 26 417–420.CrossRefGoogle Scholar
[45]Howorka, E. (1977) A characterization of Ptolemaic graphs: Survey of results. In Proc. 8th SE Conference on Combinatorics, Graph Theory, and Computing, pp. 355–361.Google Scholar
[46]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 35–53.CrossRefGoogle Scholar
[47]Las, Vergnas, M. (1979) On Eulerian partitions of graphs. In Graph Theory and Combinatorics (Wilson, R. J., ed.), Vol. 34 of Research Notes in Mathematics, Pitman Advanced Publishing Program, pp. 62–65.Google Scholar
[48]Las, Vergnas, M. (1981) Eulerian circuits of 4-valent graphs imbedded in surfaces. In Algebraic Methods in Graph Theory, Vols I, II: Szeged 1978, Vol. 25 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 451–477.Google Scholar
[49]Las, Vergnas, M. (1983) Le polynôme de Martin d'un graphe Eulérien. In Combinatorial Mathematics: Marseille–Luminy 1981, Vol. 75 of North-Holland Math. Stud., North-Holland, pp. 397–411.Google Scholar
[50]Las Vergnas, M. (1988) On the evaluation at (3,3) of the Tutte polynomial of a graph. J. Combin. Theory Ser. B 45 367–372.CrossRefGoogle Scholar
[51]Makowsky, J. A., Rotics, U., Averbouch, I. and Godlin, B. (2006) Computing graph polynomials on graphs of bounded clique-width. In Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen 2006 (Fomin, F. V., ed.), Lecture Notes in Computer Science, Springer, pp. 191–204.CrossRefGoogle Scholar
[52]Martin, P. (1977) Enumerations Eulériennes dans le multigraphs et invariants de Tutte–Grothendieck. Thesis, Grenoble.Google Scholar
[53]Martin, P. (1978) Remarkable valuation of the dichromatic polynomial of planar multigraphs. J. Combin. Theory Ser. B 24 318–324.CrossRefGoogle Scholar
[54]McKee, T. A. and McMorris, F. R. (1999) Topics in Intersection Graph Theory. SIAM Monograms on Discrete Mathematics and Applications.CrossRefGoogle Scholar
[55]Noble, S. D. (1998) Evaluating the Tutte polynomial for graphs of bounded tree-width. Combin. Probab. Comput. 7 307–321.CrossRefGoogle Scholar
[56]Oum, S. (2005) Rank-width and vertex-minors. J. Combin. Theory Ser. B 95 79–100.CrossRefGoogle Scholar
[57]Oum, S. and Seymour, P. (2006) Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96 514–528.CrossRefGoogle Scholar
[58]Oxley, J. (1982) On Crapo's beta invariant for matroids. Stud. Appl. Math. 66 267–277.CrossRefGoogle Scholar
[59]Oxley, J. G. and Welsh, D. J. A. (1992) Tutte polynomials computable in polynomial time. Discrete Math. 109 185–192.CrossRefGoogle Scholar
[60]Read, R. C. and Rosenstiehl, P. (1978) On the Gauss crossing problem. In Combinatorics II, Vol. 18 of Colloq. Math. Soc. János Bolyai, pp. 843–876.Google Scholar
[61]Read, R. C. and Rosenstiehl, P. (1978) On the principal edge tripartition of a graph. Ann. Discrete Math. 3 195–226.Google Scholar
[62]Sarmiento, I. (1998) Algebraic problems in matroid theory. D.Phil thesis, Oxford.Google Scholar
[63]Sarmiento, I. (1999) A characterisation of jointless Dowling geometries. Discrete Math. 197–198 713–731.Google Scholar
[64]Tutte, W. T. (1947) A ring in graph theory. Proc. Cambridge Philos. Soc. 43 26–40.CrossRefGoogle Scholar
[65]Tutte, W. T. (1954) A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 80–91.CrossRefGoogle Scholar
[66]Tutte, W. T. (1967) On dichromatic polynomials. J. Combin. Theory 2 301–320.CrossRefGoogle Scholar
[67]Tutte, W. T. (1979) All the king's horses: A guide to reconstruction. In Graph Theory and Related Topics: Proc. Conference at the University of Waterloo, Ont., 1977, Academic Press, pp. 15–33.Google Scholar
[68]Tuza, Z. (1997) Graph colorings with local constraints: A survey. Discuss. Math. J. Graph Theory 17 161–228.CrossRefGoogle Scholar
[69]Welsh, D. J. A. (1993) Complexity: Knots, Colorings and Counting. Vol. 186 of London Math. Soc. Lecture Notes Series, Cambridge University Press.CrossRefGoogle Scholar
[70]Wessel, W. and Pöschel, R. (1985) On circle graphs. In Graphs, Hypergraphs and Applications: Eyba 1984, Vol. 73 of Teubner-Texte Math., Teubner, pp. 207–210.Google Scholar