Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

The Linear 2-Arboricity of Planar Graphs

 Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la ₂(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la ₂(G)≤⌈(Δ+1)/2⌉+12; (2) la ₂(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la ₂(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la ₂(G)≤⌈(Δ+1)/2⌉+1 if g≥7. Received: June 28, 2001 Final version received: May 17, 2002 Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei. The financial support provided by the Institute is greatly appreciated.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

Induced Matching Extendable Graph Powers

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. We obtain the following two results which give positive answers to two conjectures of Yuan. Result 1. If a connected graph G with |V(G)| even is locally connected, then G² is strongly IM-extendable. Result 2. If G is a 2-connected graph with |V(G)| even, then G³ is strongly IM-extendable. Research Supported by NSFC Fund 10371102.     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

The number of contractible edges in 3-connected graphs

An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges.     

A [k,k+1]-factor containing given Hamiltonian cycle

Letk⩾2 be an integer and let G be a graph of ordern with minimum degree at leastk, n⩾8k -16 for evenn and n⩾6k - 13 for oddn. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycleC. G has a [k, k + 1]-factor containingC Preject supported partially by an exchange program between the Chinese Academy of Sciences and the Japan Society for Promotion of Sciences and by the National Natural Science Foundation of China (Grant No. 19136012)     

On the parallel evaluation of a sparse polynomial at a point

A new version of the Ruffini–Horner rule is presented for the evaluation of a polynomial of degree n at a point. In the PRAM model of parallel computation the new algorithm requires log n parallel steps with n/2+1 processors and the total number of arithmetic operations is n+⌈log₂(n+1)⌉ -1 multiplications and n additions. If the polynomial is sparse, i.e., the number of nonzero coefficients is k≪ n, then the total number of operations is at most k(⌈log n⌉- ⌊log k⌋)+2k+⌈log n⌉. Moreover, similarly to the customary Ruffini–Horner rule, the algorithm is backward numerically stable. In other words, the value provided by applying the algorithm in floating point arithmetic with machine precision μ coincides with the value taken on at the same point by a slightly perturbed polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.     

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 Enomoto’s problems in a bipartite graph

In this paper, we obtain the following result: Let k, n ₁ and n ₂ be three positive integers, and let G = (V ₁,V ₂;E) be a bipartite graph with |V1| = n ₁ and |V ₂| = n ₂ such that n ₁ ⩾ 2k + 1, n ₂ ⩾ 2k + 1 and |n ₁ − n ₂| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V ₁ and y ∈ V ₂ with xy $ \notin $ \notin E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

On vertex-coloring edge-weighting of graphs

A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ _e∋u w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.      

On the Caccetta–Häggkvist Conjecture

 It was conjectured by Caccetta and H?ggkvist in 1978 that every digraph G with n vertices and minimum outdegree at least r contains a directed cycle of length at most ⌈n/r⌉. By refining an argument of Chvátal and Szemerédi, we prove that such G contains a directed cycle of length at most n/r+73. Received: September 13, 1999 Final version received: June 19, 2000 Acknowledgment. I want to thank a referee for many valuable suggestions leading to the clear presentation of the paper.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.     

A vertex cover with chorded 4-cycles

Let k be an integer with k ≥ 2 and G a graph with order n > 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n + k, then G contains a vertex cover with exactly k components such that k−1 of them are chorded 4-cycles. The degree condition is sharp in general.     

The number of powers of 2 in a representation of large even integers (I)

Under the Generalized Riemann Hypothesis, it is proved that for any integer k⩾770 there is N_k>0 depending onk only such that every even integer ⩾N_k is a sum of two odd prime numbers andk powers of 2. The research is partially supported by RGC research grant (HKU 518/96P). The first author is supported by Post-Doctoral Fellowship of The University of Hong Kong.     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.