A Contribution to a Conjecture of A. Saito

 A. Saito conjectured that every finite 3-connected line graph of diameter at most 3 is hamiltonian unless it is the line graph of a graph obtained from the Petersen graph by adding at least one pendant edge to each of its vertices. Here we shall see that a line graph of connectivity 3 and diameter at most 3 has a hamiltonian path. Received: May 31, 2000 Final version received: August 17, 2001 RID="*" ID="*" This work has partially been supported by DIMATIA, Grant 201/99/0242, Grant Agency of the Czech Republic AMS subject classification: 05C45, 05C40     

On stability of the hamiltonian index under contractions and closures

The hamiltonian index of a graph G is the smallest integer k such that the k‐th iterated line graph of G is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an A_G(F)‐contractible subgraph F of a graph G nor the closure operation performed on G (if G is claw‐free) affects the value of the hamiltonian index of a graph G. AMS Subject Classification (2000): 05C45, 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Maximum Number of Contractible Edges on Hamiltonian Cycles of a 3-Connected Graph

 We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to . Received: July 31, 2000 Final version received: December 12, 2000 Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper.     

A Class of 2-Colorable Orthogonal Double Covers of Complete Graphs by Hamiltonian Paths

K _n by a graph G is a collection ? of n spanning subgraphs of K _n , all isomorphic to G, such that any two members of ? share exactly one edge and every edge of K _n is contained in exactly two members of ?. In the 1980's Hering posed the problem to decide the existence of an ODC for the case that G is an almost-hamiltonian cycle, i.e. a cycle of length n−1. It is known that the existence of an ODC of K _n by a hamiltonian path implies the existence of ODCs of K _4n and K _16n , respectively, by almost-hamiltonian cycles. Horton and Nonay introduced 2-colorable ODCs and showed: If for n≥3 and a prime power q≥5 there are an ODC of K _n by a hamiltonian path and a 2-colorable ODC of K _q by a hamiltonian path, then there is an ODC of K _qn by a hamiltonian path. We construct 2-colorable ODCs of K _n and K _2n , respectively, by hamiltonian paths for all odd square numbers n≥9. Received: January 27, 2000     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

The mixed general routing polyhedron

 In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described. Received: June 30, 1999 / Accepted: March 2002 Published online: March 21, 2003 Key Words. polyhedral combinatorics – facets – routing – arc routing – rural postman problem – general routing problem – mixed chinese postman problem     

Symmetrized Induced Ramsey Theory

We prove induced Ramsey theorems in which the monochromatic induced subgraph satisfies that all members of a prescribed set of its partial isomorphisms extend to automorphisms of the colored graph (without requirement of preservation of colors). We consider vertex and edge colorings, and extensions of partial isomorphisms in the set of all partial isomorphisms between singletons as considered by Babai and Sós (European J Combin 6(2):101–114, 1985), the set of all finite partial isomorphisms as considered by Hrushovski (Combinatorica 12(4):411–416, 1992), Herwig (Combinatorica 15:365–371, 1995) and Herwig-Lascar (Trans Amer Math Soc 5:1985–2021, 2000), and the set of all total isomorphisms. We observe that every finite graph embeds into a finite vertex transitive graph by a so called bi-embedding, an embedding that is compatible with a monomorphism between the corresponding automorphism groups. We also show that every countable graph bi-embeds into Rado’s universal countable graph Γ.     

Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

 This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Ni?o-Mora (2001): Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability), and a new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted and long-run average criteria; this gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics. Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002 RID="★" ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project 2000-20132) Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm – dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation laws – achievable performance Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08     

Circulant Double Coverings of a Circulant Graph of Valency Five

Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering graph is circulant. Recently, the authors [Discrete Math., 277, 73-85 （2004）1 enumerated the isomorphism classes of circulant double coverings of a certain type, called a typical covering, and showed that no double covering of a circulant graph of valency three is circulant. Also, in [Graphs and Combinatorics, 21,386 400 （2005）], the isomorphism classes of circulant double coverings of a circulant graph of valency four are enumerated. In this paper, the isomorphism classes of circulant double coverings of a circulant graph of valency five are enumerated.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

A Note on the Game Chromatic Index of Graphs

In this note we prove that the game chromatic index χ _g ^′(G) of a graph G of arboricity k is at most Δ + 3k − 1. This improves a bound obtained by Cai and Zhu [J. Graph Theory 36 (2001), 144–155] for k-degenerate graphs. Tomasz Bartnicki: Research of the first author is supported by a PhD grant from Polish Ministry of Science and Higher Education N201 2128 33. Received: November 1, 2006. Final version received: December 22, 2007.     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

Variations on the Theorem of Birkhoff – von Neumann and Extensions

 The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived by using elementary properties of graph theory. Received: October 10, 2000 Final version received: April 11, 2002     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999     

Hamiltonian κ-factors in graphs

Let κ ≥ 2 be an integer. A k-factor F of a graph G is called a hamiltonian k-factor if F contains a Hamiltonian cycle. In this paper, we shall prove that if G is a graph of order n with κ ≥ 2,n ≥ 8κ - 4, κn even and δ(G) ≥ n/2, then G has a hamiltonian k-factor. © 1997 Wiley & Sons, Inc. J Graph Theory 25: 217–227, 1997     

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean