Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

Triangle‐free graphs that are signable without even holes

We characterize triangle‐free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd‐signable graphs). These graphs arise as building blocks of a decomposition theorem (for cap‐free odd‐signable graphs) obtained by the same authors. We give a polytime algorithm to test membership in this class. This algorithm is itself based on a decomposition theorem. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 204–220, 2000     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable

It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4‐cycles adjacent to 3‐cycles can be covered by two induced forests. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 234–240, 2009     

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.     

Semi‐transitive graphs

In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi‐transitive and semi‐transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi‐transitive spider‐graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi‐transitive graph (if it has more than one) is a bi‐transitive graph. We show how the alternets can be used to understand the structure of a semi‐transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi‐transitive graphs of degree 4 begun by Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

Fair reception and Vizing's conjecture

In this paper we introduce the concept of fair reception of a graph which is related to its domination number. We prove that all graphs G with a fair reception of size γ(G) satisfy Vizing's conjecture on the domination number of Cartesian product graphs, by which we extend the well‐known result of Barcalkin and German concerning decomposable graphs. Combining our concept with a result of Aharoni, Berger and Ziv, we obtain an alternative proof of the theorem of Aharoni and Szabó that chordal graphs satisfy Vizing's conjecture. A new infinite family of graphs that satisfy Vizing's conjecture is also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 45‐54, 2009     

Antimagic Labelings of Join Graphs

An antimagic labeling of a graph with q edges is a bijection from the set of edges of the graph to the set of positive integers \({\{1, 2,\dots,q\}}\) such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. The join graph G + H of the graphs G and H is the graph with \({V(G + H) = V(G) \cup V(H)}\) and \({E(G + H) = E(G) \cup E(H) \cup \{uv : u \in V(G) {\rm and} v \in V(H)\}}\). The complete bipartite graph K _m,n is an example of join graphs and we give an antimagic labeling for \({K_{m,n}, n \geq 2m + 1}\). In this paper we also provide constructions of antimagic labelings of some complete multipartite graphs.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

Matching extension and minimum degree

Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

The complexity of the matching‐cut problem for planar graphs and other graph classes

The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains ‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is ‐complete for planar graphs with girth five. The reduction is from planar graph 3‐colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching‐cuts are described. These classes include claw‐free graphs, co‐graphs, and graphs with fixed bounded tree‐width or clique‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009