More results on perfect (3,3,6k + 4; 6k − 2)‐threshold schemes

A (2,3)‐packing on X is a pair (X, ), where is a set of 3‐subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. Its leave is a graph (X,E) such that E consists of all the pairs which do not appear in any block of . In this article, we shall construct a set of 6k ? 2 disjoint (2,3)‐packings of order 6k + 4 with K_1,3 ∪ 3kK₂ or G₁ ∪ (3k ? 1)K₂ as their common leave for any integer k ≥ 1 with a few possible exceptions (G₁ is a special graph of order 6). Such a system can be used to construct perfect threshold schemes as noted by Schellenberg and Stinson ( 22 ). © 2006 Wiley Periodicals, Inc. J Combin Designs     

On k‐ordered graphs

Ng and Schultz [J Graph Theory 1 ( 6 ), 45–57] introduced the idea of cycle orderability. For a positive integer k, a graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a Hamiltonian cycle, then G is said to be k‐ordered Hamiltonian. We give sum of degree conditions for nonadjacent vertices and neighborhood union conditions that imply a graph is k‐ordered Hamiltonian. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 69–82, 2000     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

Long cycles passing through vertices in k‐connected graphs

In this article, we consider the following problem proposed by Locke and Zhang in 1991: Let G be a k‐connected graph with minimum degree d and X a set of m vertices on a cycle of G. For which values of m and k, with , must G have a cycle of length at least passing through X? Fujisawa and Yamashita solved this problem for the case and in 2008. We provide an affirmative answer to this problem for the case of and .     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

There are exactly five biplanes with k = 11

A biplane is a 2‐(k(k ? 1)/2 + 1,k,2) symmetric design. Only sixteen nontrivial biplanes are known: there are exactly nine biplanes with k < 11, at least five biplanes with k = 11, and at least two biplanes with k = 13. It is here shown by exhaustive computer search that the list of five known biplanes with k = 11 is complete. This result further implies that there exists no 3‐(57, 12, 2) design, no 112₁₁ symmetric configuration, and no (324, 57, 0, 12) strongly regular graph. The five biplanes have 16 residual designs, which by the Hall–Connor theorem constitute a complete classification of the 2‐(45, 9, 2) designs. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 117–127, 2008     

Contractible subgraphs in k‐connected graphs

For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007     

Rotational k‐cycle systems of order v < 3k; another proof of the existence of odd cycle systems

We give an explicit solution to the existence problem for 1‐rotational k‐cycle systems of order v < 3k with k odd and v ≠ 2k + 1. We also exhibit a 2‐rotational k‐cycle system of order 2k + 1 for any odd k. Thus, for k odd and any admissible v < 3k there exists a 2‐rotational k‐cycle system of order v. This may also be viewed as an alternative proof that the obvious necessary conditions for the existence of odd cycle systems are also sufficient. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 433–441, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10061     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

Contractible elements in k‐connected graphs not containing some specified graphs

In 15 , Thomassen proved that any triangle‐free k‐connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k‐connected graphs which do not contain specified subgraphs. These results extend Thomassen's result, cf., 2 , 3 , 9 - 13 . In particular, Kawarabayashi 12 proved that any k‐connected graph without K subgraphs contains either a contractible edge or a contractible triangle. In this article, we further extend these results, and prove the following result. Let k be an integer with k ≥ 6. If G is a k‐connected graph such that G does not contain as a subgraph and G does not contain as an induced subgraph, then G has either a contractible edge which is not contained in any triangle or a contractible triangle. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:97–109, 2008     

1‐rotational k‐factorizations of the complete graph and new solutions to the Oberwolfach problem

We consider k‐factorizations of the complete graph that are 1‐rotational under an assigned group G, namely that admit G as an automorphism group acting sharply transitively on all but one vertex. After proving that the k‐factors of such a factorization are pairwise isomorphic, we focus our attention to the special case of k = 2, a case in which we prove that the involutions of G necessarily form a unique conjugacy class. We completely characterize, in particular, the 2‐factorizations that are 1‐rotational under a dihedral group. Finally, we get infinite new classes of previously unknown solutions to the Oberwolfach problem via some direct and recursive constructions. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 87–100, 2008     

Y‐rotation in k‐minimal quadrangulations on the projective plane

Let G be a quadrangulation on a surface, and let f be a face bounded by a 4‐cycle abcd. A face‐contraction of f is to identify a and c (or b and d) to eliminate f. We say that a simple quadrangulation G on the surface is k‐minimal if the length of a shortest essential cycle is k(≥3), but any face‐contraction in G breaks this property or the simplicity of the graph. In this article, we shall prove that for any fixed integer k≥3, any two k‐minimal quadrangulations on the projective plane can be transformed into each other by a sequence of Y‐rotations of vertices of degree 3, where a Y‐rotation of a vertex v of degree 3 is to remove three edges vv₁, vv₃, vv₅ in the hexagonal region consisting of three quadrilateral faces vv₁v₂v₃, vv₃v₄v₅, and vv₅v₆v₁, and to add three edges vv₂, vv₄, vv₆. Actually, every k‐minimal quadrangulation (k≥4) can be reduced to a (k?1)‐minimal quadrangulation by the operation called Möbius contraction, which is mentioned in Lemma 13. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 301–313, 2012     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Packing k‐edge trees in graphs of restricted vertex degrees

Let denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τ_k (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that

• (a1) if G ∈ and s ≥ 4, then τ₂(G) ≥ v(G)/(s + 1),
• (a2) if G ∈ and G has no 5‐vertex components, then τ₂(G) ≥ v(G)4,
• (a3) if G ∈ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τ_k(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and
• (a4) the above bounds are attained for infinitely many connected graphs.

Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Proof of Mader's conjecture on k‐critical n‐connected graphs

Mader conjectured that every k‐critical n‐connected noncomplete graph G has 2k + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of G is greater than (k + 2)n. Now we settle this conjecture completely. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 281–297, 2004     

Solution of the Ulam stability problem for Euler–Lagrange–Jensen k‐quintic mappings

In this paper, we are introducing pertinent Euler–Lagrange–Jensen type k‐quintic functional equations and investigate the ‘Ulam stability’ of these new k‐quintic functional mappings f:X→Y, where X is a real normed linear space and Y a real complete normed linear space. We also solve the Ulam stability problem for Euler–Lagrange–Jensen alternative k‐quintic mappings. Copyright © 2016 John Wiley & Sons, Ltd.