On a connection between the existence ofk-trees and the toughness of a graph

A graphG has toughnesst(G) ift(G) is the largest numbert such that for any subsetS of the vertices ofG, the number of vertices inS is at leastt times the number of components ofG on deletion of the vertices inS, provided that there is then more than one component. Ak-tree of a connected graph is a spanning tree with maximum degree at mostk. We show here that if , withk 3, thenG has ak-tree. The notion of ak-tree generalizes the casek = 2 of a hamiltonian path, so that this result, as we discuss, may be of some interest in connection with Chvátal's conjecture that, for somet, every graph with toughness at leastt is hamiltonian.     

Proof of the Seymour conjecture for large graphs

Paul Seymour conjectured that any graphG of ordern and minimum degree of at leastk/k+1n contains thekth power of a Hamiltonian cycle. Here, we prove this conjecture for sufficiently largen.     

On the number of homogeneous subgraphs of a graph

Let us defineG(n) to be the maximum numberm such that every graph onn vertices contains at leastm homogeneous (i.e. complete or independent) subgraphs. Our main result is exp (0.7214 log² n) ≧G(n) ≧ exp (0.2275 log² n), the main tool is a Ramsey—Turán type theorem. We formulate a conjecture what supports Thomason’s conjecture R(k, k)^1/k = 2.     

Graphs isomorphic to subgraphs of their iterated line graphs

A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK _1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL ⁿ(G).     

Maximal Total Length Of k Disjoint Cycles In Bipartite Graphs

Let k, s and n be three integers with sk2, n2k+1. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n. If the minimum degree of G is at least s+1, then G contains k vertex-disjoint cycles covering at least min(2n,4s) vertices of G.     

On thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

On the graph of large distances

For a setS of points in the plane, letd ₁>d ₂>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd _k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk ². IfS consists of the vertices of a convex polygon and |S|constk ², then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.     

Connectivity keeping edges in graphs with large minimum degree

The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G−v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least 3k/2+2. Then G has an edge e such that G−V(e) is still k-connected.The bound on the minimum degree is essentially best possible.     

On long cycles in a 2-connected bipartite graph

Letk be an integer withk 2. LetG = (A, B; E) be a 2-connected bipartite graph. Supposed(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy. ThenG contains a cycle of length at leastmin(2a, 2k) wherea = min(|A|,|B|), unlessG is one of some known exceptions. We conjecture that if|A| = |B| andd(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy withx A andy B, thenG contains a cycle of length at leastmin(2a, 2k).     

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)     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

On the convergence order of accelerated root iterations

Summary A Gauss-Seidel procedure for accelerating the convergence of the generalized method of the root iterations type of the (k+2)-th order (kN) for finding polynomial complex zeros, given in [7], is considered in this paper. It is shown that theR-order of convergence of the accelerated method is at leastk+1+ _n (k), where _n (k)>1 is the unique positive root of the equation ⁿ --k-1 = 0 andn is the degree of the polynomial. The examples of algebraic equations in ordinary and circular arithmetic are given.     

Some simple in-place merging algorithms

The theoretical presentation and analysis is given for two families of simple in-place merging algorithms and their limiting cases. The first family merges stably inO(k·n) time andO(n ^1/k ) additional space with a limiting case running inO(n logn) time and constant space. The second family merges unstably inO (k ·n) time andO(log ^k n) space with a limiting case running inO(nG(n)) time and constant space. HereG(n) is the leastk such thatF(k) n whereF(0)=1 andF(i)=2 ^F(i–1) fori1. Each algorithm gives rise to a corresponding merge sort.     

On the number of independent chorded cycles in a graph

Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp.     

Minimal Degree and (k, m)-Pancyclic Ordered Graphs

Given positive integers k m n, a graph G of order n is (k, m)-pancyclic ordered if for any set of k vertices of G and any integer r with m r n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k, m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided.     

Vertex‐disjoint cycles of length at most four each of which contains a specified vertex*

We obtain a sharp minimum degree condition δ (G) ≥ of a graph G of order n ≥ 3k guaranteeing that, for any k distinct vertices, G contains k vertex‐disjoint cycles of length at most four each of which contains one of the k prescribed vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 37–47, 2001     

A lower bound on solutions of Chartrand's problem

In this paper it is shown that if a connected graphG without loops contains spanning trees withm andn end-vertices, respectively, withm, thenG contains at least spanning trees withk end-vertices for every integerk withm where is the circuit rank ofG.     

The dimension of intersections of convex sets

In this paper we determine the smallest numberh=h(k, n) having the following property: IfG is any finite family of convex sets in Euclideann-space, and if the intersection of everyh or fewer members of ailenG is at leastk-dimensional, then the intersection of all members ofG is at leastk-dimensional. The contents of this paper forms part of the M.Sc. thesis written by the author under the supervision of Professor Micha A. Perles at the Hebrew University of Jerusalem and submitted in October, 1968.     

Vertex‐disjoint cycles containing prescribed vertices

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4k ? 1 is at least the integer , then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck² where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003