A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Total Edge Irregularity Strength of Toroidal Fullerene

A toroidal fullerene (toroidal polyhex) is a cubic bipartite graph embedded on the torus such that each face is a hexagon. An edge irregular total k-labeling of a graph G is such a labeling of the vertices and edges with labels 1, 2, … , k that the weights of any two different edges are distinct, where the weight of an edge is the sum of the label of the edge itself and the labels of its two endvertices. The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength, tes(G). In this paper we determine the exact value of the total edge irregularity strength of toroidal polyhexes.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

On the Strong Product of a k-Extendable and an l-Extendable Graph

 Let G ₁⊗G ₂ be the strong product of a k-extendable graph G ₁ and an l-extendable graph G ₂, and X an arbitrary set of vertices of G ₁⊗G ₂ with cardinality 2[(k+1)(l+1)/2]. We show that G ₁⊗G ₂−X contains a perfect matching. It implies that G ₁⊗G ₂ is [(k+1)(l+1)/2]-extendable, whereas the Cartesian product of G ₁ and G ₂ is only (k+l+1)-extendable. As in the case of the Cartesian product, the proof is based on a lemma on the product of a k-extendable graph G and K ₂. We prove that G⊗K ₂ is (k+1)-extendable, and, a bit surprisingly, it even remains (k+1)-extendable if we add edges to it. Received: February 17, 1997 Final version received: June 14, 2000     

Counting perfect matchings in n-extendable graphs

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G.     

The 2-extendability of 5-connected graphs on surfaces with large representativity

A graph with at least 2k+2 vertices is said to be k-extendable if any independent set of k edges in it extends to a perfect matching. We shall show that every 5-connected graph G of even order embedded on a closed surface F², except the sphere, is 2-extendable if ρ(G)?7−2χ(F²), where ρ(G) stands for the representativity of G on F² and χ(F²) for the Euler characteristic of F².     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

A note on n-extendable graphs

A graph G having a perfect matching is called n-extendable if every matching of size n of G can be extended to a perfect matching. In this note, we show that if G is an n-extendable nonbipartite graph, then G + e is (n - 1)-extendable for any edge e ? E(G). © 1992 John Wiley & Sons, Inc.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

Heilbronn's conjecture on Waring's number (mod p)

Let p be a prime k|p−1, t=(p−1)/k and γ(k,p) be the minimal value of s such that every number is a sum of s kth powers . We prove Heilbronn's conjecture that γ(k,p)?k1/2 for t>2. More generally we show that for any positive integer q, γ(k,p)?C(q)k1/q for ?(t)?q. A comparable lower bound is also given. We also establish exact values for γ(k,p) when ?(t)=2. For instance, when t=3, γ(k,p)=a+b−1 where a>b>0 are the unique integers with a²+b²+ab=p, and when t=4, γ(k,p)=a−1 where a>b>0 are the unique integers with a²+b²=p.     

The 2-extendability of 5-connected graphs on the Klein bottle

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. In this paper, we shall characterize the forbidden structures for 5-connected graphs on the Klein bottle to be 2-extendable. This fact also gives us a sharp lower bound of representativity of 5-connected graphs embedded on the Klein bottle to have such a property, which was considered in Kawarabayashi et al. (submitted for publication) [4].     

Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

2-resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes

A set H of disjoint faces of a plane bipartite graph G is a resonant pattern if G has a perfect matching M such that the boundary of each face in H is an M-alternating cycle. An elementary result was obtained [Discrete Appl. Math. 105 (2000) 291-311]: a plane bipartite graph is 1-extendable if and only if every face forms a resonant pattern. In this paper we show that for a 2-extendable plane bipartite graph, any pair of disjoint faces form a resonant pattern, and the converse does not necessarily hold. As an application, we show that all boron-nitrogen (B-N) fullerene graphs are 2-resonant, and construct all the 3-resonant B-N fullerene graphs, which are all k-resonant for any positive integer k. Here a B-N fullerene graph is a plane cubic graph with only square and hexagonal faces, and a B-N fullerene graph is k-resonant if any disjoint faces form a resonant pattern. Finally, the cell polynomials of 3-resonant B-N fullerene graphs are computed.     

A note on internally disjoint alternating paths in bipartite graphs

Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let x∈X and y∈Y. Let k be a positive integer. Then we prove that if G has k internally disjoint alternating paths between x and y with respect to some perfect matching, then G has k internally disjoint alternating paths between x and y with respect to every perfect matching.     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

Perfect matchings in large uniform hypergraphs with large minimum collective degree

We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.