A generalization of Hungarian method and Hall’s theorem with applications in wireless sensor networks

In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall’s marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum $g$-quasi-matching (that is a set $F$ of edges in a bipartite graph such that in one set of the bipartition every vertex $v$ has at least $g\left(v\right)$ incident edges from $F$, where $g$ is a so-called need mapping, while on the other side of the bipartition the distribution of degrees with respect to $F$ is lexicographically minimum). We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement: the optima of any component-based strictly convex cost function on any subset of $L_1$-sphere in ${\mathbb{N}}^n$ are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks.     

Chromatic-index-critical graphs of orders 13 and 14

A graph is chromatic-index-critical if it cannot be edge-coloured with Δ colours (with Δ the maximal degree of the graph), and if the removal of any edge decreases its chromatic index. The Critical Graph Conjecture stated that any such graph has odd order. It has been proved false and the smallest known counterexample has order [[18] A.J.W. Hilton, R.J. Wilson, Edge-colorings of graphs: a progress report, in: M.F. Cabobianco, et al. (Eds.), Graph Theory and its Applications: East and West, New York, 1989, pp. 241–249; [31] H.P. Yap, Some topics in graph theory, London Mathematical Society, Lecture Note Series, vol. 108, Cambridge University Press, Cambridge, 1986].

In this paper we show that there are no chromatic-index-critical graphs of order 14. Our result extends that of [[5] G. Brinkmann, E. Steffen, Chromatic-index-critical graphs of orders 11 and 12, European J. Combin. 19 (1998) 889–900] and leaves order 16 as the only case to be checked in order to decide on the minimality of the counterexamples given by Chetwynd and Fiol. In addition we list all nontrivial critical graphs of order 13.     

Principal/Two-Agent model with internal signal

Central European Journal of Operations Research - Our novel game-theoretic Principal/Two-Agent model ensures that the Principal has a reliable internal signal about the Agents’ invested work...     

Infinite families of crossing‐critical graphs with prescribed average degree and crossing number

?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010     

General Lower Bounds for the Minor Crossing Number of Graphs

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs and establish a lower bound for the standard crossing number in terms of Randič index.     

The circular chromatic number of a digraph

We introduce the circular chromatic number χ_c of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χ_c between 1 and 2 are possible. We show that in fact, χ_c takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χ_c at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004     

Crossing number additivity over edge cuts

Consider a graph G$G$ with a minimal edge cut F$F$ and let _G1$G_1$, _G2$G_2$ be the two (augmented) components of G−F$G-F$. A long-open question asks under which conditions the crossing number of G$G$ is (greater than or) equal to the sum of the crossing numbers of _G1$G_1$ and _G2$G_2$—which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|∈{0,1,2}$\left|F\right|\in \{0,1,2\}$ and that there exist graphs violating this property with |F|≥4$\left|F\right|\ge 4$. In this paper, we show that crossing number is additive for |F|=3$\left|F\right|=3$, thus closing the final gap in the question.     

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007