A unified approach to known and unknown cases of Berge's conjecture

Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition P of the vertex set of a digraph minimizing , there exists a collection C^k of k disjoint independent sets, where each dipath P∈P meets exactly min{|P|, k} of the independent sets in C. This conjecture extends Linial's conjecture, the Greene–Kleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for acyclic digraphs. For general digraphs, it is known for k=1 by the Gallai–Milgram Theorem, for k?λ (where λis the number of vertices in the longest dipath in the graph), by the Gallai–Roy Theorem, and when the optimal path partition P contains only dipaths P with |P|?k. Recently, it was proved (Eur J Combin (2007)) for k=2. There was no proof that covers all the known cases of Berge's conjecture. In this article, we give an algorithmic proof of a stronger version of the conjecture for acyclic digraphs, using network flows, which covers all the known cases, except the case k=2, and the new, unknown case, of k=λ?1 for all digraphs. So far, there has been no proof that unified all these cases. This proof gives hope for finding a proof for all k.     

Characterization of n-path graphs and of graphs having nth root

We characterize connected graphs and digraphs having an nth root and so generalize results by A. Mukhopadhyay and D. P. Geller, respectively. We then define the n-path graph of a graph and characterize those graphs which are n-path graphs. This extends recent results by B. Devadas Acharya and M. N. Vartak. The corresponding problem for digraphs is also considered.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.     

Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.     

Representation of MV-algebras by regular ultrapowers of [0, 1]

We present a uniform version of Di Nola Theorem, this enables to embed all MV-algebras of a bounded cardinality in an algebra of functions with values in a single non-standard ultrapower of the real interval [0,1]. This result also implies the existence, for any cardinal α, of a single MV-algebra in which all infinite MV-algebras of cardinality at most α embed. Recasting the above construction with iterated ultrapowers, we show how to construct such an algebra of values in a definable way, thus providing a sort of “canonical” set of values for the functional representation.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

On the number of paths and cycles for almost all graphs and digraphs

In this paper it is deduced the number ofs-paths (s-cycles) havingk edges in common with a fixeds-path (s-cycle) of the complete graphK _n (orK* _n for directed graphs). It is also proved that the number of the common edges of twos-path (s-cycles) randomly chosen from the set ofs-paths (s-cycles) ofK _n (respectivelyK* _n ), are random variables, distributed asymptotically in accordance with the Poisson law whenever s/n exists, thus extending a result by Baróti. Some estimations of the numbers of paths and cycles for almost all graphs and digraphs are made by applying Chebyshev’s inequality.     

HSAGA and its application for the construction of near-Moore digraphs

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions.This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems.     

Improved lower bounds on k-independence

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)-graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.     

Any 7-Chromatic Graphs Has K 7 Or K 4,4 As A Minor

In 1943, Hadwiger made the conjecture that every k-chromatic graph has a K _k -minor. This conjecture is, perhaps, the most interesting conjecture of all graph theory. It is well known that the case k=5 is equivalent to the Four Colour Theorem, as proved by Wagner [39] in 1937. About 60 years later, Robertson, Seymour and Thomas [29] proved that the case k=6 is also equivalent to the Four Colour Theorem. So far, the cases k7 are still open and we have little hope to verify even the case k=7 up to now. In fact, there are only a few theorems concerning 7-chromatic graphs, e. g. [17].In this paper, we prove the deep result stated in the title, without using the Four Colour Theorem [1,2,28]. This result verifies the first unsettled case m=6 of the (m,1)-Minor Conjecture which is a weaker form of Hadwigers Conjecture and a special case of a more general conjecture of Chartrand et al. [8] in 1971 and Woodall [42] in 1990.The proof is somewhat long and uses earlier deep results and methods of Jørgensen [20], Mader [23], and Robertson, Seymour and Thomas [29].* Research partly supported by the Japan Society for the Promotion of Science for Young Scientists. Research partly supported by the Danish Natural Science Research Council.Dedicated to Professor Mike Plummer on the occasion of his sixty-fifth birthday.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

An upper bound for the total chromatic number of dense graphs

In this paper we consider those graphs that have maximum degree at least 1/k times their order, where k is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex-colorings and an adaptation of the standard proof of Vizing's Theorem are used to show that if the maximum degree of a graph G satisfies Δ(G) ≥ |V(G)/k, then X″(G) ≤ Δ(G) + 2k + 1. This upper bound is an improvement on the currently available upper bounds for dense graphs having large order.     

Menger's Theorem

Menger's Theorem for digraphs states that for any two vertex sets A and B of a digraph D such that A cannot be separated from B by a set of at most t vertices, there are t + 1 disjoint A–B‐paths in D. Here a short and elementary proof of a more general theorem is given. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 35–36, 2001     

On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces

 We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P _k , a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m. Received: June 29, 1998 Final version received: April 11, 2000     

A Local Property of Large Polyhedral Maps on Compact 2-Dimensional Manifolds

We prove that each polyhedral map G on a compact 2-manifold, which has large enough vertices, contains a k-path, a path on k vertices, such that each vertex of it has, in G, degree at most 6k; this bound being best possible for k even. Moreover, if G has large enough vertices of degree >6k, than it contains a k-path such that each its vertex has degree, in G, at most 5k; this bound is best possible for any k. Received: December 8, 1997 Revised: April 27, 1998     

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.     

Multi-latin squares

A multi-latin square of order n and index k is an n×n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in k-latin square of order m embeds in a k-latin square of order n, for each n≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥k+2. We also show that for each n≥1, there exists some finite value g(n) such that for all k≥g(n), every k-latin square of order n is separable.We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.     

The kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs

In this article, we study the kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs. A bound on the kth upper bases for primitive nonpowerful minimally strong signed digraphs is obtained, and the equality case of the bound is characterized. For the kth lower bases, we obtain some bounds. For some cases, the bounds are best possible and the extremal signed digraphs are characterized. We also show that there exist ‘gaps’ in both the kth upper base set and the kth lower base set of primitive nonpowerful minimally strong signed digraphs.     

The Erdős‐Sós Conjecture for trees of diameter four

The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005