Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

Absolute Lipschitz extendability

A metric space X is said to be absolutely Lipschitz extendable if every Lipschitz function f from X into any Banach space Z can be extended to any containing space Y?X, where the loss in the Lipschitz constant in the extension is independent of $\text{Y,}\text{Z}$, and f. We show that various classes of natural metric spaces are absolutely Lipschitz extendable. To cite this article: J.R. Lee, A. Naor, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Hamiltonian decompositions of strong products

It is shown that if both G₁ and G₂ are Hamiltonian decomposable, then so is their strong product. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 45–55, 1998     

一类泛圈图

本文证明了如果 Ｇ 是 ２ 连通无爪图, Ｇ 不是圈,ｎ＝ ｜ Ｖ（ Ｇ）｜≥９, Ｇ 的每个导出子图 Ａ都满足φ（ａ１,ａ２ ）,且 Ｇ 中不含同构于 Ｚ＋２ 的导出子图,则 Ｇ是泛圈图     

纽立方体网络的容错泛圈性

互连网络包含所有可能长度的圈是一个重要的拓扑性质。纽立方体网络TOn是超立方体网络Qn的一种变型,其中n≥3是奇数。Chang等人[Information Science,113(1999),147-167]证明了TOn中包含任意长度为l的圈,其中4≤l≤2n。如果TOn中的故障点数和故障边数之和不超过(n-2),Huang等人[J.Parallel andDistributed Computing,62(2002),591-640]证明了:TQn中包含长度为2n-fv的圈,其中fv是故障点数。这篇文章改进这些结果为:TQn中包含任意长度为l的圈,其中4≤l≤2n-fv。     

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.     

Pancyclicity of connected circulant graphs

The circulant G_n(a₁, ⋖, a_k), where 0 < a₁ < ··· < a_k < (n + 1)/2, is defined as the vertex-transitive graph that has vertices i ± a₁, ···, i ± a_k(mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In addition, we prove that the connected circulants of girth three contain cycles of all lengths. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 17–25, 1997     

The extendability of S-plurisubharmonic currents

In this Note we are interested in studying the extension of negative S-plurisubharmonic currents across closed sets.     

Path extendability of claw-free graphs

Let G be a connected, locally connected, claw-free graph of order n and x,y be two vertices of G. In this paper, we prove that if for any 2-cut S of G, S∩{x,y}=∅, then each (x,y)-path of length less than n-1 in G is extendable, that is, for any path P joining x and y of length h(<n-1), there exists a path P^′ in G joining x and y such that V(P)⊂V(P^′) and |P^′|=h+1. This generalizes several related results known before.     

On the extendability of code isometries

A block codeC F ⁿ is calledmetrically rigid, if every isometry: CF ⁿ with respect to theHamming metric is extendable to an isometry of the whole spaceF ⁿ . The metrical rigidity of some classes of codes is discussed.Dedicated to Helmut Karzel on the occasion of his 70th birthdayResearch supported by the Russian Foundation of Fundamental Research (Grant no. 97-01-01104)Research supported by the Russian Foundation of Fundamental Research (Grants no. 96-01-01800, 97-01-01075)     

On the extendability of steiner t-designs

Necessary and sufficient conditions for the extendability of residual designs of Steiner systems S(t,t + 1,v) are studied. In particular, it is shown that a residual design with respect to a single point is uniquely extendable, and the extendability of a residual design with respect to a pair of points is equivalent to a bipartition of the block graph of a related design. © 1993 John Wiley & Sons, Inc.     

On the Pancyclicity of Lexicographic Products

We prove that if G and H are graphs containing at least one edge each, then their lexicographic product G[H] is weakly pancyclic, i. e., it contains a cycle of every length between the length of a shortest cycle and that of a longest one. This supports some conjectures on locally connected graphs and on product graphs. We obtain an analogous result on even cycles in products G[H] that are bipartite. We also investigate toughness conditions on G implying that G[H] is hamiltonian (and hence pancyclic). Supported by the project LN00A056 of the Czech Ministry of Education     

Pancyclicity of Strong Products of Graphs

We prove that the strong product of graphs G₁××G_n is pancyclic, in particular hamiltonian, for nc for any cln(25/12)+1/640.75 whenever all G_i are connected graphs with the maximum degree at most .This research was supported by KONTAKT ME 337 as a part of REU programme and in part by GACR 201/99/0242The author acknowledges partial support by NSF grant DMS-9900969 and by Institute for Theoretical Computer ScienceThe author acknowledges partial support by Institute for Theoretical Computer ScienceInstitute for Theoretical Computer Science is supported by Ministry of Education of Czech Republic as project LN00A056Final version received: August 6, 2003     

An extendability condition for bilipschitz functions

We give a new definition of λ-relatively connected set, some generalization of a uniformly perfect set. This definition is equivalent to the old definition for large λ but makes it possible to obtain stable properties for small λ. We prove the λ-relative connectedness of Cantor sets for corresponding λ. The main result is as follows: A ? ? admits the extension of all M-bilipschitz functions f: A → ? to M-bilipschitz functions F: ? → ? if and only if A is λ-relatively connected. We give exact estimates of the dependence of M and λ.     

On wedge extendability of CR-meromorphic functions

In this article, we consider metrically thin singularities E of the solutions of the tangential Cauchy-Riemann operators on a -smooth embedded Cauchy-Riemann generic manifold M (CR functions on ) and more generally, we consider holomorphic functions defined in wedgelike domains attached to . Our main result establishes the wedge- and the L¹-removability of E under the hypothesis that the -dimensional Hausdorff volume of E is zero and that M and are globally minimal. As an application, we deduce that there exists a wedgelike domain attached to an everywhere locally minimal M to which every CR-meromorphic function on M extends meromorphically. Received: 7 September 2000; in final form: 20 December 2001 / Published online: 6 August 2002     

On an extendability problem for measures

We prove a theorem stating a sufficient condition for the existence of an extension of a probability measure, and we use this result to answer a question concerning such extensions in the negative.Finally, I would like to thank Professor M.P. Jerschow for pointing (*) out to me and for an interesting discussion on this topic.