[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

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

Abstract

A graph \(G=(V,E)\) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Alom BMM, Das S, Islam MS (2010) Finding the maximum matching in a bipartite graph. DUET J 1(1):33–36

    Google Scholar 

  • Amjadi J, Nazari-Moghaddam S, Sheikholeshami SM (2017) Global total Roman domination in graphs. Discrete Math Algorithms Appl 9(4):1750050

    Article  MathSciNet  MATH  Google Scholar 

  • de Carvalho MH, Lucchesi CL, Murty USR (2005) On the number of dissimilar Pfaffian orientations of graphs. RAIRO Inf Theor Appl 39:93–113

    Article  MathSciNet  MATH  Google Scholar 

  • Kasteleyn PW (1961) The statistics of dimers on a lattice. I. The number of dimer arrangments on a quadratic lattice. Physica 27:1209–1225

    Article  MATH  Google Scholar 

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

    Google Scholar 

  • Krishnakumari B, Chellali M, Venkatakrishnan YB (2017) Double vertex-edge domination. Discrete Math Algorithms Appl 9(4):1750045

    Article  MathSciNet  MATH  Google Scholar 

  • Lin F, Zhang L, Lu F (2014) Pfaffian orientations for a type of bipartite graph. Theoret Comput Sci 527:97–101

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Lovász L (1987) Matching structure and the matching lattice. J Comb Theory Ser B 43:187–222

    Article  MathSciNet  MATH  Google Scholar 

  • Lovász L, Plummer MD (1986) Matching theory. North-Holland, Amsterdam

    MATH  Google Scholar 

  • Lu FL, Zhang LZ (2014) The Pfaffian property of Cartesian products of graphs. J Comb Optim 27:530–540

    Article  MathSciNet  MATH  Google Scholar 

  • Lu FL, Zhang LZ, Wang Y (2015) The Pfaffian property of circulant graphs. Discrete Appl Math 181:185–192

    Article  MathSciNet  MATH  Google Scholar 

  • McCuaig W (2004) Pólya’s permanent problem. Electron J Comb 11:R79

  • Norine S (2005) Matching structure and Pfaffian orientations of graphs, Doctoral dissertation. Georgia Institute of Technology

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

    Article  MathSciNet  MATH  Google Scholar 

  • Valiant LG (1979) The complexity of computing the permanent. Theoret Comput Sci 8:189–201

    Article  MathSciNet  MATH  Google Scholar 

  • Vazirani VV, Yannakakis M (1989) Pfaffian orientations, 0–1 permanents, and even cycles in directed graphs. Discrete Appl Math 25:179–190

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang LZ, Wang Y, Lu FL (2012) Pfaffian graphs embedding on the torus. Sci China Math 56:1957–1964

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are grateful to the anonymous referees for their careful reading and many helpful suggestions that greatly improved our original manuscript.

Author information

Authors and Affiliations

  1. School of Mathematical Science, Xiamen University, Xiamen, 361005, China

    Xing Feng, Lianzhu Zhang & Mingzu Zhang

Authors
  1. Xing Feng
    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

  3. Mingzu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lianzhu Zhang.

Additional information

The research is supported by National Natural Science Foundation of China (Grant Nos. 11171279, 11471273).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Feng, X., Zhang, L. & Zhang, M. An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs. J Comb Optim 35, 740–753 (2018). https://doi.org/10.1007/s10878-017-0207-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-017-0207-0

Keywords

Search

Navigation