1,721,513 research outputs found
On Determinants and Permanents of Minimally 1-Factorable Cubic Bipartite Graphs
No full textA minimally 1-factorable cubic bigraph is a graph in which every 1-factor lies in precisely one 1-factorization. The author investigates determinants and permanents of such graphs and, in particular, proves that the determinant of any minimally 1-factorable cubic bigraph of girth 4 is 0
Corrigendum to "Graphs and digraphs with all 2--factors isomorphic" [J. of Comb. Th. Ser. B 92, (2) (2004) 395--404]
No full textWe point out several errors in our article [M. Abreu, R.E.L. Aldred, M. Funk, B. Jackson, D. Labbate, J. Sheehan, Graphs and digraphs with all 2-factor isomorphic, J. Combin. Theory Ser. B 92 (2004) 395–404] which were caused by our misquoting of a theorem of C. Thomassen. We also describe how the correct statement of Thomassen’s theorem, together with another of his theorems, can be used to obtain weaker results than those incorrectly stated in our original article
A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
No full textA graph admiting a -factor is \textit{pseudo -factor isomorphic} if
the parity of the number of cycles in all its -factors is the same. In [M.
Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo -factor
isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B,
98(2) (2008), 432-444.] some of the authors of this note gave a partial
characterisation of pseudo -factor isomorphic bipartite cubic graphs and
conjectured that , the Heawood graph and the Pappus graph are the only
essentially -edge-connected ones. In [J. Goedgebeur. A counterexample to the
pseudo -factor isomorphic graph conjecture. Discr. Applied Math., 193
(2015), 57-60.] Jan Goedgebeur computationally found a graph on
vertices which is pseudo -factor isomorphic cubic and bipartite,
essentially -edge-connected and cyclically -edge-connected, thus refuting
the above conjecture. In this note, we describe how such a graph can be
constructed from the Heawood graph and the generalised Petersen graph
, which are the Levi graphs of the Fano configuration and the
M\"obius-Kantor configuration, respectively. Such a description of
allows us to understand its automorphism group, which has order
, using both a geometrical and a graph theoretical approach
simultaneously. Moreover we illustrate the uniqueness of this graph
On 3-Cut Reductions of Minimally 1-Factorable Cubic Bigraphs
No full textAbstractA cubic bigraph G is minimally 1-factorable if every 1-factor lies in precisely one 1-factorization. We characterize 3-bridges of G and prove that the 3-cut reductions of G are still minimally 1-factorable; thus, the open classification problem is reduced to the study of 3-bridge-free minimally 1-factorable cubic bigraphs. Furthermore, we prove that if ab, cd are edges of G such that the graph obtained by twisting them in ad, bc is still minimally 1-factorable, then ab, cd lie in some 3-bridge of G
Characterizing Minimally 1-factorable r-Regular Bipartite Graphs
No full textAbstractThe possibilities for circuits of length 4 to appear together in a cubic bigraph are classified. That has consequences on the structure of minimally 1-factorable regular bigraphs, i.e. those in which each 1-factor lies in precisely one 1-factorization. We characterize minimally 1-factorable cubic bigraphs of girth 4
- …
