×

A characterisation of Pfaffian near bipartite graphs. (English) Zbl 1024.05077

If \(v\) and \(w\) are vertices in a directed graph, then we denote by \((v,w)\) an edge directed from \(v\) to \(w\). Now let \(G^*\) be a directed graph with an even number \(2n\) of vertices and let \(F\) be the set \(\{f_1,f_2,\dots, f_k\}\) of 1-factors of \(G^*\). For all \(i\) write \[ f_i= \{(u_{i1}, w_{i1}), (u_{i2}, w_{i2}),\dots, (u_{in}, w_{in})\}, \] where \(u_{ij}\) and \(w_{ij}\) are vertices of \(G^*\) for each \(j\). Associate with \(f_i\) a plus sign if \[ u_{i1} w_{i1} u_{i2} w_{i2}\cdots u_{in} w_{in} \] is an even permutation of \[ u_{11} w_{11} u_{12} w_{12}\cdots u_{1n} w_{1n}, \] and a minus sign otherwise. An undirected graph is said to be Pfaffian if it has an orientation under which all the 1-factors have the same sign. Pfaffian orientations have been used by P. W. Kasteleyn [Graph Theory Theor. Phys., 43-110 (1967; Zbl 0205.28402)] to enumerate 1-factors in a graph. A graph is 1-extendible if every edge has a 1-factor containing it. A 1-extendible non-bipartite graph \(G\) is said to be near bipartite if there exists \(e_1\) and \(e_2\) such that \(G- \{e_1,e_2\}\) is 1-extendible and bipartite. We characterise the Pfaffian near bipartite graphs in terms of forbidden subgraphs. The theorem extends an earlier characterisation of Pfaffian bipartite graphs.

MSC:

05C75 Structural characterization of families of graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0205.28402
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Kasteleyn, P. W., Graph theory and crystal physics, (Harary, F., Graph Theory and Theoretical Physics (1967), Academic Press: Academic Press New York), 43-110 · Zbl 0205.28402
[2] Little, C. H.C., Kasteleyn’s theorem and arbitrary graphs, Canad. J. Math., 25, 758-764 (1973) · Zbl 0275.05115
[3] Little, C. H.C., A characterization of convertible (0, 1)-matrices, J. Combin. Theory Ser. B, 18, 187-208 (1975) · Zbl 0281.05013
[4] C. H. C. Little, F. Rendl, and, I. Fischer, Towards a characterisation of Pfaffian graphs, Discrete Math, to appear.; C. H. C. Little, F. Rendl, and, I. Fischer, Towards a characterisation of Pfaffian graphs, Discrete Math, to appear. · Zbl 0997.05084
[5] Lovász, L.; Plummer, M. D., Matching Theory (1986), Akadémiai Kiadó: Akadémiai Kiadó Budapest · Zbl 0618.05001
[6] W. McCuaig, Pólya’s permanent problem, manuscript, 1997.; W. McCuaig, Pólya’s permanent problem, manuscript, 1997.
[7] Robertson, N.; Seymour, P. D.; Thomas, R., Permanents, Pfaffian orientations and even directed circuits, Ann. Math. (2), 150, 929-975 (1999) · Zbl 0947.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.