Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Pfaffian property of Cartesian products of graphs

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

Suppose that G=(V,E) is a graph with even vertices. An even cycle C is a nice cycle of G if G−V(C) has a perfect matching. An orientation of G is a Pfaffian orientation if each nice cycle C has an odd number of edges directed in either direction of the cycle. Let P n and C n denote the path and the cycle on n vertices, respectively. In this paper, we characterize the Pfaffian property of Cartesian products G×P 2n and G×C 2n for any graph G in terms of forbidden subgraphs of G. This extends the results in (Yan and Zhang in Discrete Appl Math 154:145–157, 2006).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  • Fischer I, Little CHC (2001) A characterisation of Pfaffian near bipartite graphs. J Comb Theory, Ser B 82:175–222

    Article  MATH  MathSciNet  Google Scholar 

  • Fischer I, Little CHC (2003) Even circuits of prescribed clockwise parity. Electron J Comb 10:#R45

    MathSciNet  Google Scholar 

  • Kasteleyn PW (1961) The statistics of dimers on a lattice. Physica A 12:1209–1225

    Google Scholar 

  • Kasteleyn PW (1967) Graph theory and crystal physics. In: Harary F (ed) Graph theory and theoretical physics. Academic Press, San Diego, pp 43–110

    Google Scholar 

  • Lin F, Zhang L (2009) Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs. Electron J Comb 16:#R52

    Google Scholar 

  • Little CHC (1975) A characterization of convertible (0,1)-matrices. J Comb Theory, Ser B 18:187–208

    Article  MATH  MathSciNet  Google Scholar 

  • Little CHC, Rendl F (1991) Operations preserving the Pfaffian property of a graph. J Aust Math Soc A 50:248–257

    Article  MATH  MathSciNet  Google Scholar 

  • Lovász L, Plummer M (1986) Matching theory. Ann of Discrete Math, vol 29. North-Holland, New York

    MATH  Google Scholar 

  • McCuaig W, Robertson N, Seymour PD, Thomas, R (1997) Permanents, Pfaffian orientations, and even directed circuits (Extended abstract). In: Proc symposium on the theory of computing (STOC)

  • Norine S, Thomas R (2008) Minimally non-Pfaffian graphs. J Comb Theory, Ser B 98:1038–1055

    Article  MATH  MathSciNet  Google Scholar 

  • Robertson R, Seymour PD, Thomas R (1999) Permanents, Pfaffian orientations, and even directed circuits. Ann Math 150:929–975

    Article  MATH  MathSciNet  Google Scholar 

  • Yan W, Zhang F (2004) Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians. Adv Appl Math 32:655–668

    Article  MATH  Google Scholar 

  • Yan W, Zhang F (2006) Enumeration of perfect matchings of a type of Cartesian products of graphs. Discrete Appl Math 154:145–157

    Article  MATH  MathSciNet  Google Scholar 

  • Zhang L, Wang Y, Lu F (2012) Pfaffian graphs embedding on the torus (submitted)

Download references

Author information

Authors and Affiliations

  1. School of Sciences, Linyi University, Linyi, Shandong, 276000, China

    Fuliang Lu

  2. School of Mathematical Sciences, Xiamen University, Xiamen, Fujian, 361005, China

    Lianzhu Zhang

Authors
  1. Fuliang Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lianzhu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lianzhu Zhang.

Additional information

This work is supported by NSFC (No. 10831001; No. 11171279).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lu, F., Zhang, L. The Pfaffian property of Cartesian products of graphs. J Comb Optim 27, 530–540 (2014). https://doi.org/10.1007/s10878-012-9533-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-012-9533-4

Keywords

Search

Navigation