On signed digraphs with all cycles negative

In “On signed digraphs with all cycles negative”, Discrete Appl. Math. 12 (1985) 155–164, F. Harary, J.R. Lundgren and J.S. Maybee, identify certain families of such digraphs: the class of strong and upper digraphs and the class Ū. We give here a characterization of the latter class and new proofs of two results concerning these classes, by using the c-minimal strongly connected digraphs. This note answers some questions of the authors.     

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

Graham and Pollak [2] proved that n – 1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n decompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.     

Algebraic K-theory of groups wreath product with finite groups

The Farrell-Jones Fibered Isomorphism Conjecture for the stable topological pseudoisotopy theory has been proved for several classes of groups. For example, for discrete subgroups of Lie groups [F.T. Farrell, L.E. Jones, Isomorphism conjectures in algebraic K-theory, J. Amer. Math. Soc. 6 (1993) 249-297], virtually poly-infinite cyclic groups [F.T. Farrell, L.E. Jones, Isomorphism conjectures in algebraic K-theory, J. Amer. Math. Soc. 6 (1993) 249-297], Artin braid groups [F.T. Farrell, S.K. Roushon, The Whitehead groups of braid groups vanish, Internat. Math. Res. Notices 10 (2000) 515-526], a class of virtually poly-surface groups [S.K. Roushon, The isomorphism conjecture for 3-manifold groups and K-theory of virtually poly-surface groups, math.KT/0408243, K-Theory, in press] and virtually solvable linear group [F.T. Farrell, P.A. Linnell, K-Theory of solvable groups, Proc. London Math. Soc. (3) 87 (2003) 309-336]. We extend these results in the sense that if G is a group from the above classes then we prove the conjecture for the wreath product G?H for H a finite group. The need for this kind of extension is already evident in [F.T. Farrell, S.K. Roushon, The Whitehead groups of braid groups vanish, Internat. Math. Res. Notices 10 (2000) 515-526; S.K. Roushon, The Farrell-Jones isomorphism conjecture for 3-manifold groups, math.KT/0405211, K-Theory, in press; S.K. Roushon, The isomorphism conjecture for 3-manifold groups and K-theory of virtually poly-surface groups, math.KT/0408243, K-Theory, in press]. We also prove the conjecture for some other classes of groups.     

A characterization of graphs of competition number m

In this note we give a characterization of graphs with competition number less than or equal to m. We also give an alternate proof of a theorem characterizing competition graphs.     

Maximum Directed Cuts in Graphs with Degree Constraints

The Max Cut problem is an NP-hard problem and has been studied extensively. Alon et?al. (J Graph Theory 55:1–13, 2007) studied a directed version of the Max Cut problem and observed its connection to the Hall ratio of graphs. They proved, among others, that if an acyclic digraph has m edges and each vertex has indegree or outdegree at most 1, then it has a directed cut of size at least 2m/5. Lehel et?al. (J Graph Theory 61:140–156, 2009) extended this result by replacing the “acyclic digraphs” with the “digraphs containing no directed triangles”. In this paper, we characterize the acyclic digraphs with m edges whose maximum dicuts have exactly 2m/5 edges, and our approach gives an alternative proof of the result of Lehel et?al. We also show that there are infinitely many positive rational numbers β < 2/5 for which there exist digraphs D (with directed triangles) such that each vertex of D has indegree or outdegree at most 1, and any maximum directed cut in D has size precisely β|E(D)|.     

The constructive characterization of (��,?)-edge-connected digraphs

We give a constructive characterization for (??, ?)-edge-connected digraphs, proving a conjecture of Frank.     

The competition numbers of complete tripartite graphs

For a graph G, it is known to be a hard problem to compute the competition number k(G) of the graph G in general. In this paper, we give an explicit formula for the competition numbers of complete tripartite graphs.     

Recognizing digraphs of Kelly-width 2

Kelly-width is a parameter of digraphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give an alternative characterization of digraphs of bounded Kelly-width in support of this analogy, and the first polynomial-time algorithm recognizing digraphs of Kelly-width 2. For an input digraph G=(V,A) the algorithm outputs a vertex ordering and a digraph H=(V,B) with A⊆B witnessing either that G has Kelly-width at most 2 or that G has Kelly-width at least 3, in time linear in H.     

Kernels and perfectness in arc-local tournament digraphs

In this paper we give a characterization of kernel-perfect (and of critical kernel-imperfect) arc-local tournament digraphs. As a consequence, we prove that arc-local tournament digraphs satisfy a strenghtened form of the following interesting conjecture which constitutes a bridge between kernels and perfectness in digraphs, stated by C. Berge and P. Duchet in 1982: a graph G is perfect if and only if any normal orientation of G is kernel-perfect. We prove a variation of this conjecture for arc-local tournament orientable graphs. Also it is proved that normal arc-local tournament orientable graphs satisfy a stronger form of Berge's strong perfect graph conjecture.     

Adjusted Interval Digraphs

Interval digraphs were introduced by West et al. They can be recognized in polynomial time and admit a characterization in terms of incidence matrices. Nevertheless, they do not have a forbidden structure characterization nor a low-degree polynomial recognition algorithm.We introduce a new class of ‘adjusted interval digraphs,’ obtained by a slight change in the definition. We show that, by contrast, these digraphs have a natural forbidden structure characterization, parallel to a characterization for undirected graphs, and admit a simple recognition algorithm. We relate adjusted interval digraphs to a list homomorphism problem. Each digraph H defines a corresponding list homomorphism problem L-HOM(H). We observe that if H is an adjusted interval digraph, then the problem L-HOM(H) is polynomial time solvable, and conjecture that for all other reflexive digraphs H the problem L-HOM(H) is NP-complete. We present some preliminary evidence for the conjecture, including a proof for the special case of semi-complete digraphs.     

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.     

An algorithm for finding hamilton cycles in random directed graphs

We describe a polynomial (O(n^1.5)) time algorithm DHAM for finding hamilton cycles in digraphs. For digraphs chosen uniformly at random from the set of digraphs with vertex set {1, 2, …, n} and m = m(n) edges the limiting probability (as n → ∞) that DHAM finds a hamilton cycle equals the limiting probability that the digraph is hamiltonian. Some applications to random “travelling salesman problems” are discussed.     

Compactified Jacobians and q,t-Catalan numbers, II

We continue the study of the rational-slope generalized q,t-Catalan numbers c _m,n (q,t). We describe generalizations of the bijective constructions of J. Haglund and N. Loehr and use them to prove a weak symmetry property c _m,n (q,1)=c _m,n (1,q) for m=kn±1. We give a bijective proof of the full symmetry c _m,n (q,t)=c _m,n (t,q) for min(m,n)≤3. As a corollary of these combinatorial constructions, we give a simple formula for the Poincaré polynomials of compactified Jacobians of plane curve singularities x ^kn±1=y ⁿ . We also give a geometric interpretation of a relation between rational-slope Catalan numbers and the theory of (m,n)-cores discovered by J. Anderson.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Matrices A for which the upper bound per(A)?1+min{Π(c_i?1), Π(r_i?1)} holds with equality are characterized. Cases where the bound is achieved correspond to multigraphs with the property that there exists a unique path from any vertex to any disjoint cycle union. This occurs precisely when some multigraph associated with A has the mastercycle property: all cycles thread all branchpoints in the same circular order. Such multigraphs may also be characterized as a circular concatenation of certain acyclic multigraphs, each having a unique source and sink. This analysis yields two normal forms for the extremal matrices, one based on a nested block decomposition, and another based on an overlapping block decomposition. The extremal cases are invariant under contractions, yielding another characterization.     

Salem numbers defined by Coxeter transformation

A real algebraic integer α>1 is called a Salem number if all its remaining conjugates have modulus at most 1 with at least one having modulus exactly 1. It is known [J.A. de la Peña, Coxeter transformations and the representation theory of algebras, in: V. Dlab et al. (Eds.), Finite Dimensional Algebras and Related Topics, Proceedings of the NATO Advanced Research Workshop on Representations of Algebras and Related Topics, Ottawa, Canada, Kluwer, August 10-18, 1992, pp. 223-253; J.F. McKee, P. Rowlinson, C.J. Smyth, Salem numbers and Pisot numbers from stars, Number theory in progress. in: K. Gy?ry et al. (Eds.), Proc. Int. Conf. Banach Int. Math. Center, Diophantine problems and polynomials, vol. 1, de Gruyter, Berlin, 1999, pp. 309-319; P. Lakatos, On Coxeter polynomials of wild stars, Linear Algebra Appl. 293 (1999) 159-170] that the spectral radii of Coxeter transformation defined by stars, which are neither of Dynkin nor of extended Dynkin type, are Salem numbers. We prove that the spectral radii of the Coxeter transformation of generalized stars are also Salem numbers. A generalized star is a connected graph without multiple edges and loops that has exactly one vertex of degree at least 3.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

An extension of bipartite multigraphs

Usual edge colorings have been generalized in various ways; we will consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k ? 2. This implies that they also have a good k-coloring for each k ? 2. In this paper, we characterize a class of multigraphs which may be considered as a generalization of bipartite multigraphs, in the sense that for each k ? 2 they have a good k-coloring. A more restrictive class is derived where all multigraphs have an equitable k-coloring for each k ? 2.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

Claws in digraphs

We study in this Note the existence of claws in digraphs. We extend a result of Saks and Sós to the tournament-like digraphs. To cite this article: A. El Sahili, M. Kouider, C. R. Acad. Sci. Paris, Ser. I 346 (2008).