Search

In 1986, Thomassen posed the following conjecture: every 4-connected line graph has a Hamiltonian cycle. As a possible approach to the conjecture, many researchers have considered statements that are equivalent or related to it. One of them is the conjecture by Bondy: there exists a constant $c_0$ with $0 < c_0 \leq 1$ such that every cyclically 4-edge-connected cubic graph $H$ has a cycle of length at least $c_0 |V(H)|$. It is known that Thomassen's conjecture implies Bondy's conjecture, but nothing about the converse has been shown. In this paper, we show that Bondy's conjecture implies a slightly weaker version of Thomassen's conjecture: every 4-connected line graph with minimum degree at least 5 has a Hamiltonian cycle.

International audience; Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, “hardwired” and “softwired,” and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available.

Hat problems have recently become a popular topic in combinatorics and discrete mathematics. These have been shown to be strongly related to coding theory, network coding, and auctions. We consider the following version of the hat game, introduced by Winkler and studied by Butler et al. A team is composed of several players; each player is assigned a hat of a given colour; they do not see their own colour, but can see some other hats, according to a directed graph. The team wins if they have a strategy such that, for any possible assignment of colours to their hats, at least one player guesses their own hat colour correctly. In this paper, we discover some new classes of graphs which allow a winning strategy, thus answering some of the open questions in Butler et al. We also derive upper bounds on the maximal number of possible hat colours that allow for a winning strategy for a given graph.

This paper continues the study of Fourier transforms on finite inverse semigroups, with a focus on Fourier inversion theorems and FFTs for new classes of inverse semigroups. We begin by introducing four inverse semigroup generalizations of the Fourier inversion theorem for finite groups. Next, we describe a general approach to the construction of fast inverse Fourier transforms for finite inverse semigroups complementary to an approach to FFTs given in previous work. Finally, we give fast inverse Fourier transforms for the symmetric inverse monoid and its wreath product by arbitrary finite groups, as well as fast Fourier and inverse Fourier transforms for the planar rook monoid, the partial cyclic shift monoid, and the partial rotation monoid., Comment: v2: Streamlined presentation and added results for the planar rook monoid, partial cyclic shift monoid, and partial rotation monoid. 24 pages

Chordal graphs have been extensively studied and have applications in various fields, including computational biology, sparse matrix computation, and graphical models. They are characterized by the existence of clique trees, whose vertices correspond to the maximal cliques of a chordal graph. In many applications, it is the clique tree of the chordal graph that is of greatest utility. In general, the number of clique trees can grow exponentially with the size of the chordal graph, and in some applications, particular clique trees have greater utility; we want additional criteria to select the most useful clique tree(s). A natural criterion in phylogenetics (and perhaps elsewhere) is that of compactness. In this paper, we formalize this criterion as the average distance between nodes, and present a characterization of clique trees that satisfies this criterion. We also develop a polynomial-time algorithm to find such a clique tree, and show that any minimum average-distance clique tree of a chordal graph c...

Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order ${n_{_H}} = |V|$ and size ${m_{_H}} = |E|$. The hypergraph $H$ is $k$-uniform if every edge of $H$ has size $k$. Two vertices in $H$ are adjacent if they belong to a common edge in $H$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A total transversal in $H$ is a transversal $T$ in $H$ with the additional property that every vertex in $T$ is adjacent to some other vertex of $T$. The total transversal number $\tau_t(H)$ of $H$ is the minimum cardinality of a total transversal in $H$. For $k \ge 2$, let $b_k = \sup_{H \in {\cal H}_k} \, {\tau_t}(H) / ({n_{_H}} + {m_{_H}})$, where ${\cal H}_k$ denotes the class of all $k$-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that $b_2 = 2/5$, $b_3 = 1/3$, $b_4 \le 1/3$, and $b_5 \le 2/7$. In this paper, we show that $b_4 = 2/7$ and $b_6 \le 1/4$. Further, for $k \ge 7$, we ...

A famous conjecture of P\'osa from 1962 asserts that every graph on $n$ vertices and with minimum degree at least $2n/3$ contains the square of a Hamilton cycle. The conjecture was proven for large graphs in 1996 by Koml\'os, S\'ark\"ozy and Szemer\'edi. In this paper we prove a degree sequence version of P\'osa's conjecture: Given any $\eta >0$, every graph $G$ of sufficiently large order $n$ contains the square of a Hamilton cycle if its degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq (1/3+\eta)n+i$ for all $i \leq n/3$. The degree sequence condition here is asymptotically best possible. Our approach uses a hybrid of the Regularity-Blow-up method and the Connecting-Absorbing method., Comment: 52 pages, 5 figures, to appear in SIAM J. Discrete Math

Tutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.

We study the effect of boundary conditions on the relaxation time (i.e., inverse spectral gap) of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter $\lambda$, called the activity or fugacity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor $b$, the hard-core model can be equivalently defined as a broadcasting process with a parameter $\omega$ which is the positive solution to $\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability $\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and nonreconstruction regions at $\omega_r\approx \ln{b}/b$. Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular trees $T_h$ of height $h$ with branching factor $b$ and $n$ vertices undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any $\omega \le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta + o_b(1)})$, and we construct a boundary condition where the relaxation time is $\Omega(n^{1+\delta/2 - o_b(1)})$. To prove this lower bound in the reconstruction region we introduce a general technique that transforms a reconstruction algorithm into a set with poor conductance.

M.A. Henning and A. Yeo conjectured in SIAM J. Discrete Math., 26 (2012), pp. 687--694] that a digraph of minimum out-degree at least 4, contains two vertex-disjoint cycles of different lengths. In this paper we prove this conjecture. The main tool is a new result (to our knowledge) asserting that in a digraph $D$ of minimum out-degree at least $4$, there exist two vertex-disjoint cycles $C_1$ and $C_2$, a path $P_1$ from a vertex $x$ of $C_1$ to a vertex $z$ not in $V(C_1)\cup V(C_2)$, and a path $P_2$ from a vertex $y$ of $C_2$ to $z$, such that $V(P_1)\cap (V(C_1)\cup V(C_2))=\lbrace x\rbrace$, $V(P_2)\cap (V(C_1)\cup V(C_2))=\lbrace y\rbrace$, and $V(P_1)\cap V(P_2)=\lbrace z\rbrace$. In the last section, a conjecture will be proposed.

The classical paradox of social choice theory asserts that there is no fair way to deterministically select a winner in an election among more than two candidates; the only definite collective preferences are between individual pairs of candidates. Combinatorially, one may summarize this information with a graph-theoretic tournament on N vertices (one per candidate), placing an edge from U to V if U would beat V in an election between only those two candidates (no ties are permitted). One well-studied procedure for selecting a winner is to specify a complete binary tree whose leaves are labeled by the candidates, and evaluate it by running pairwise elections between the pairs of leaves, sending the winners to successive rounds of pairwise elections which ultimately terminate with a single winner. This structure is called a voting tree. Much research has investigated which functions on tournaments are computable in this way. Fischer, Procaccia, and Samorodnitsky quantitatively studied the computability of the Copeland rule, which returns a vertex of maximum out-degree in the given tournament. Perhaps surprisingly, the best previously known voting tree could only guarantee a returned out-degree of at least log_2 N, despite the fact that every tournament has a vertex of degree at least (N-1)/2. In this paper, we present three constructions, the first of which substantially improves this guarantee to \Theta(sqrt{N}). The other two demonstrate the richness of the voting tree universe, with a tree that resists manipulation, and a tree which implements arithmetic modulo three., Comment: 13 pages

Bicontactual regular maps (regular maps with the property that each face meets only two others) were introduced and classified by Wilson in 1985. This property generalizes to hypermaps (cellular embeddings of hypergraphs in compact surfaces) giving rise to three types of bicontactuality, namely, the edge-twin, the vertex-twin, and the alternate (the first two of which are the dual of each other). In 2003 Wilson and Breda classified (up to an isomorphism and duality) the bicontactual regular nonorientable hypermaps, leaving the orientable case open. In this paper we classify the bicontactual regular oriented hypermaps.

One of the main problems we want to address is the fact that in the construction theory of authentication codes, the expression “new code” is used all the time, while it is almost never shown that the obtained codes indeed are new, or even what the notion “new” means to begin with. In this paper, we formally define authentication codes and introduce a comparison method for them, using the notion of isomorphism and the invariant isomorphism group. We then define operations in this framework which enable us to “multiply” and “add” arbitrary authentication codes, regardless of how they are initially constructed. We obtain (nonisomorphic) codes with easily calculated parameters, a large number of which are new.

Finding a forbidden subgraph characterization of circular-arc graphs is a challenging open problem. Many partial results toward this goal have been proposed over the years, but a satisfactory answer has so far eluded us. In this paper, we suggest a new direction in this line of research. We propose a novel structural obstruction to circular-arc graphs---a blocking quadruple---and study its use in characterizing circular-arc graphs within chordal graphs. Notably, we observe that the absence of blocking quadruples unifies characterizations of various known chordal subclasses of circular-arc graphs found in the literature. To this end, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples and show that the absence of blocking quadruples exactly characterizes chordal circular-arc graphs of independence number 4 or less. Our proof uses an interesting geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tre...

An $(a:b)$-coloring of a graph $G$ is a function $f$ which maps the vertices of $G$ into $b$-element subsets of some set of size $a$ in such a way that $f(u)$ is disjoint from $f(v)$ for every two adjacent vertices $u$ and $v$ in $G$. The fractional chromatic number $\chi_f(G)$ is the infimum of $a/b$ over all pairs of positive integers $a,b$ such that $G$ has an $(a:b)$-coloring. Heckman and Thomas conjectured that the fractional chromatic number of every triangle-free graph $G$ of maximum degree at most three is at most 2.8. Hatami and Zhu proved that $\chi_f(G) \leq 3-3/64 \approx 2.953$. Lu and Peng improved the bound to $\chi_f(G) \leq 3-3/43 \approx 2.930$. Recently, Ferguson, Kaiser and Kr\'{a}l' proved that $\chi_f(G) \leq 32/11 \approx 2.909$. In this paper, we prove that $\chi_f(G) \leq 43/15 \approx 2.867$.

In 2006, Kuhn and Osthus [J. Combin. Theory Ser. B, 96 (2006), pp. 767--821] showed that if a 3-graph $H$ on $n$ vertices has minimum codegree at least $(1/4 +o(1))n$ and $n$ is even, then $H$ has a loose Hamilton cycle. In this paper, we prove that the minimum codegree of $n/4$ suffices. The result is tight.

We consider the problems of completing a low-rank positive semidefinite square matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. Following the approach initiated by Singer and Cucuringu [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1621--1641] we study the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries of $M$ or $N$. We present combinatorial characterizations of local and global (unique) completability for special families of graphs. We characterize local and global completability in all dimensions for cluster graphs, i.e. graphs which can be obtained from disjoint complete graphs by adding a set of independent edges. These results correspond to theorems for body-bar frameworks in rigidity theory. We also provide a characterization of two-dimensional local completability of planar bipartite graphs, which leads to a characterization of two-dimensional local completability in the rectangular matrix model when the underlying bipartite graph is planar. These results are based on new observations that certain graph operations preserve local or global completability, as well as on a further connection between rigidity and completability. We also prove that a rank condition on the completability stress matrix of a graph is a sufficient condition for global completability. This verifies a conjecture of Singer and Cucuringu given in the paper cited above.

In this paper we prove an Erdős-Ko-Rado-type theorem for intersecting sets of permutations. We show that an intersecting set of maximal size in the projective general linear group \(PGL_3(q)\), in its natural action on the points of the projective line, is either a coset of the stabilizer of a point or a coset of the stabilizer of a line. This gives the first evidence to the veracity of Conjecture~\(2\) from K.~Meagher, P.~Spiga, An Erdős-Ko-Rado theorem for the derangement graph of \(\mathrm{PGL}(2,q)\) acting on the projective line, \( \textit{J. Comb. Theory Series A} \textbf{118} \) (2011), 532--544. Faculty yes

Schnyder characterized planar graphs in terms of order dimension. The structures used for the proof have found many applications. Researchers also found several extensions of the seminal result. A particularly far-reaching extension is the Brightwell--Trotter theorem about planar maps. It states that the order dimension of the incidence poset $\mathbf{P}_{\mathbf{M}}$ of vertices, edges, and faces of a planar map $\mathbf{M}$ has dimension at most 4. The original proof generalizes the machinery of Schnyder paths and Schnyder regions. In this short paper we use a simple result about the order dimension of grid intersection graphs to show a slightly stronger result: $\dim(\mathsf{split}(\mathbf{P}_{\mathbf{M}})) \leq 4$. Here, $\mathsf{split}(P)$ refers to a particular order of height two associated with $P$. The Brightwell--Trotter theorem follows because $\dim(\mathsf{split}(P)) \geq \dim(P)$ holds for every $P$. This may be the first result in the area that is obtained without using the tools introduced ...

In this paper we consider spectral extremal problems for hypergraphs. We give two general criteria under which such results may be deduced from `strong stability' forms of the corresponding (pure) extremal results. These results hold for the \alpha-spectral radius defined using the \alpha-norm for any \alpha>1; the usual spectrum is the case \alpha=2. Our results imply that any hypergraph Tur\'{a}n problem which has the stability property and whose extremal construction satisfies some rather mild continuity assumptions admits a corresponding spectral result. A particular example is to determine the maximum \alpha-spectral radius of any 3-uniform hypergraph on n vertices not containing the Fano plane, when n is sufficiently large. Another is to determine the maximum \alpha-spectral radius of any graph on n vertices not containing some fixed colour-critical graph, when n is sufficiently large; this generalizes a theorem of Nikiforov who proved stronger results in the case \alpha=2. We also obtain an \alpha-spectral version of the Erd\H{o}s-Ko-Rado theorem on t-intersecting k-uniform hypergraphs., Comment: 20 pages

An undirected graph is Eulerian if it is connected and all its vertices are of even degree. Similarly, a directed graph is Eulerian, if for each vertex its in-degree is equal to its out-degree. It is well known that Eulerian graphs can be recognized in polynomial time while the problems of finding a maximum Eulerian subgraph or a maximum induced Eulerian subgraph are NP-hard. In this paper, we study the parameterized complexity of the following Euler subgraph problems: - Large Euler Subgraph: For a given graph G and integer parameter k, does G contain an induced Eulerian subgraph with at least k vertices? - Long Circuit: For a given graph G and integer parameter k, does G contain an Eulerian subgraph with at least k edges? Our main algorithmic result is that Large Euler Subgraph is fixed parameter tractable (FPT) on undirected graphs. We find this a bit surprising because the problem of finding an induced Eulerian subgraph with exactly k vertices is known to be W[1]-hard. The complexity of the problem changes drastically on directed graphs. On directed graphs we obtained the following complexity dichotomy: Large Euler Subgraph is NP-hard for every fixed k>3 and is solvable in polynomial time for k

The matching forest problem in mixed graphs is a common generalization of the matching problem in undirected graphs and the branching problem in directed graphs. Giles presented an $\mathrm{O}(n^{2}m)$-time algorithm for finding a maximum-weight matching forest, where $n$ is the number of vertices and $m$ is that of edges, and a linear system describing the matching forest polytope. Later, Schrijver proved total dual integrality of the linear system. In the present paper, we reveal another nice property of matching forests: the degree sequences of the matching forests in any mixed graph form a delta-matroid, and the weighted matching forests induce a valuated delta-matroid. We remark that the delta-matroid is not necessarily even, and the valuated delta-matroid induced by weighted matching forests slightly generalizes the well-known notion of Dress and Wenzel's valuated delta-matroids. By focusing on the delta-matroid structure and reviewing Giles' algorithm, we design a simpler $\mathrm{O}(n^{2}m)$-time ...

Ivanyos, Karpinski, and Saxena [SIAM J. Comput., 39 (2010), pp. 3736--3751] have developed a deterministic polynomial time algorithm for finding scalars $x_1, \dots, x_n$ that maximize the rank of the matrix $B_0 + x_1B_1 + \dots + x_nB_n$ for given matrices $B_0, B_1, \dots, B_n$, where $B_1, \dots, B_n$ are of rank one. Their algorithm runs in $O(m^{4.37}n)$ time, where $m$ is the larger of the row size and the column size of the input matrices. In this paper, we present a new deterministic algorithm that runs in $O((m+n)^{2.77})$ time, which is faster than the previous algorithm unless $n$ is much larger than $m$. Our algorithm makes use of an efficient completion method for mixed matrices. As an application of our completion algorithm, we devise a deterministic algorithm for the multicast problem with linearly correlated sources. We also consider a skew-symmetric version: maximize the rank of the matrix $B_0+ x_1B_1 + \dots + x_nB_n$ for given skew-symmetric matrices $B_0, B_1, \dots, B_n$, where $B_1...

A plane graph $G$ is entirely $k$-colorable if $V(G)\cup E(G) \cup F(G)$ can be colored with $k$ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph $G$ with maximum degree $\Delta\ge 12$ is entirely $(\Delta+2)$-colorable. In this paper, we improve this result by showing that every plane graph $G$ with $\Delta\ge 9$ is entirely $(\Delta+2)$-colorable.

Given an undirected graph $G=(V, E)$ and a delta-matroid $(V,{\cal F})$, the delta-matroid matching problem is to find a maximum cardinality matching $M$ such that the set of the end vertices of $M$ belongs to ${\cal F}$. This problem is a natural generalization of the matroid matching problem to delta-matroids, and thus it cannot be solved in polynomial time in general. This paper introduces a class of the delta-matroid matching problem, where the given delta-matroid is a projection of a linear delta-matroid. We first show that it can be solved in polynomial time if the given linear delta-matroid is generic. This result enlarges a polynomially solvable class of matching problems with precedence constraints on vertices such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

Let H-n be a k-graph on n vertices. For 0 infinity) ex(l)(n, F)/kappa(n-l). In this paper, we show that for k > l > 1, the set of pi(kappa)(l) (F) is dense in the interval [0, 1). Hence, there is no "jump" for l-degree Turan density when k > l > 1. We also give a lower bound on pi(kappa)(l) (F) in terms of an ordinary Turan density.

In this paper we are interested in algorithms for finding $2$-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained $2$-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight $2$-factor covering all the $3$-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the $3$- and $4$-edge cuts in bridgeless cubic graphs. Both of these algorithms run in ${\rm O}(n\sp{3})$ time, where $n$ is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4...

An independence system $\mathcal{F}$ is one of the most fundamental combinatorial concepts, which includes a variety of objects in graphs and hypergraphs such as matchings, stable sets, and matroids. We discuss the robustness for independence systems, which is a natural generalization of the greedy property of matroids. For a real number $\alpha> 0$, a set $X\in\mathcal{F}$ is said to be $\alpha$-robust if for any $k$, it includes an $\alpha$-approximation of the maximum $k$-independent set, where a set $Y$ in $\mathcal{F}$ is called $k$-independent if the size $|Y|$ is at most $k$. In this paper, we show that every independence system has a $1/\sqrt{\mu(\mathcal{F})}$-robust independent set, where $\mu(\mathcal{F})$ denotes the exchangeability of $\mathcal{F}$. Our result contains a classical result for matroids and the ones of Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530--537] for matchings and Fujita, Kobayashi, and Makino [SIAM J. Discrete Math., 27 (2013), pp. 1234--1256] for mat...

This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length $h$. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability ...

In this paper we consider an extremal problem regarding multigraphs with edge multiplicity bounded by a positive integer $q$. Given a family $\mathscr{F}$ of $q$-multigraphs, define $ex(n,\mathscr{F})$ to be the maximum number of edges (counting multiplicities) that a $q$-multigraph on $n$ vertices can have without containing a copy of any $F \in \mathscr{F}$ (not necessarily induced). It is well known that $\tau(\mathscr{F}) = \lim_{n \to \infty} ex(n,\mathscr{F})/\binom{n}{2}$ exists for every family $\mathscr{F}$ (finite or infinite). Let $\mathscr{T} = \{\tau(\mathscr{F}) : \mathscr{F} \textrm{ is a family of $q$-multigraphs}\}$. We say the number $\alpha$, $0 \leq \alpha \alpha$, then $\alpha' \geq \alpha + c$. The Erdos--Stone theorem implies that for $q=1$, every $\alpha \in [0,1)$ is a jump. The problem of determining the set of jumps for $q \geq 2$ appears to be much ha...

For a subset $A$ of the set of positive integers, a graph $G$ is called $A$-coverable if $G$ has a cycle (a subgraph in which all vertices have even degree) which intersects all edge-cuts $T$ in $G$ with $|T| \in A$, and $A$ is said to be coverable if all graphs are $A$-coverable. As a possible approach to the dominating cycle conjecture, Kaiser and Skrekovski conjectured in [SIAM J. Discrete Math., 22 (2008), pp. 861--874] that $\mathbb{N} +3$ is coverable, where $\mathbb{N} +3 = \{4,5,6, \ldots\}$. In this paper, we disprove Kaiser and Skrekovski's conjecture by showing that there exist infinitely many graphs which are not $\{4,5\}$-coverable.

Given $n_{f}$ sites, each equipped with one facility, and $n_{c}$ cities, fault tolerant facility location (FTFL) [K. Jain and V. V. Vazirani, APPROX '$00$: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, Spinger, New York, 2000, pp. 177--183] requires computing a minimum-cost connection scheme such that each city connects to a specified number of facilities. When each city connects to exactly one facility, FTFL becomes the classical uncapacitated facility location problem (UFL) that is well-known NP hard. The current best solution to FTFL admits an approximation ratio 1.7245 due to Byrka, Srinivasan, and Swamy applying the dependent rounding technique announced recently [Proceedings of IPCO, 2010, pp. 244--257], which improves the ratio 2.076 obtained by Swamy and Shmoys based on LP rounding [ACM Trans. Algorithms, 4 (2008), pp. 1--27]. In this paper, we study a variant of the FTFL problem, namely, fault tolerant facility allocation (FTFA), as a...

For a spanning tree $T$ of a graph $G$, we define the total excess $te(T,k)$ of $T$ from $k$ as $te(T,k) := \sum_{v \in V(T)} \max \{d_T(v)-k, 0\}$, where $d_T(v)$ is the degree of a vertex $v$ in $T$. In this paper, we show the following: if $G$ is a $3$-connected graph on a surface with Euler characteristic $\chi < 0$, then $G$ has a spanning $\lceil\frac{8-2\chi}{3}\rceil$-tree $T$ with $te(T, 3) \leq -2\chi-1$. We also show an application of this theorem to finding “light” connected subgraphs in a $3$-connected graph on a surface.

In this paper we show that, with 11 exceptions, any matching covered bipartite graph on $n$ vertices, with minimum degree greater than two, has at least $2n-4$ perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124--169] on brace generation, we show that any brace on $n$ vertices has at least $(n-2)^2/8$ perfect matchings. A bi-wheel on $n$ vertices has $(n-2)^2/4$ perfect matchings. We conjecture that there exists an integer $N$ such that every brace on $n\geq N$ vertices has at least $(n-2)^2/4$ perfect matchings.

We study the problem of finding the breakpoint median for multichromosomal unsigned genomes that contain circular or mixed (circular and linear) chromosomes. It has been shown by Tannier, Zheng, and Sankoff that for signed multichromosomal circular or mixed genomes the breakpoint median can be found in polynomial time; however, the complexity of the unsigned versions of the problems were unknown. In this paper, we show that these problems can all be solved in polynomial time. We also study restricted versions of the multichromosomal breakpoint median problem where the number of chromosomes of the median must be a certain number. We show that as soon as we impose a fixed number of chromosomes the problem becomes NP-hard. Moreover, we introduce the notion of partially signed circular or mixed genomes, where both signed and unsigned genes may exist in the same genome. We provide the first study of this form of these breakpoint median problems and show that these problem can also be solved in polynomial time ...

Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1990. They have been developed by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is s-overlap cycles, which relax such a constraint. In this paper we study weak orders, which are relations that are transitive and complete. We prove the existence of universal and s-overlap cycles for weak orders, as well as for fixed height and/or weight weak orders, and apply the results to cycles for ordered partitions as well., Comment: 12 pages; final version

A graph $G$ of order $n$ is said to be $\Sigma^{'}$ labeled if there exist a bijection $f:V(G)\rightarrow [n]$ and a constant $c$ such that for all $v\in V(G)$, $\sum_{u\in N[v]} f(u)=c$. The uniqueness of the constant $c$ has been an open question that was posed by Prof. Arumugam at the 2010 IWOGL Conference in Duluth. The question of the uniqueness of such a constant can be extended to arbitrary neighborhoods and to arbitrary sets of labels. For a set $D\subset \mathbb{N}$, let $N_D(v)=\{u\in V(G):d(u,v)\in D\}$, and let $W$ be a multiset of real numbers. Graph $G$ is said to be $(D,W)$-vertex magic if there exists a bijection $g:V(G)\rightarrow W$ such that for all $v\in V(G)$, $\sum_{u\in N_D(v)}g(u)$ is a constant, called the $(D,W)$-vertex magic constant. In this paper we prove that, even for these more general conditions, a $(D,W)$-vertex magic constant will be unique. Moreover, the constant can be determined using a generalization of the fractional domination number of the graph.

A number of fields, including the study of genome rearrangements and the design of interconnection networks, deal with the connected problems of sorting permutations in "as few moves as possible", using a given set of allowed operations, or computing the number of moves the sorting process requires, often referred to as the \emph{distance} of the permutation. These operations often act on just one or two segments of the permutation, e.g. by reversing one segment or exchanging two segments. The \emph{cycle graph} of the permutation to sort is a fundamental tool in the theory of genome rearrangements, and has proved useful in settling the complexity of many variants of the above problems. In this paper, we present an algebraic reinterpretation of the cycle graph of a permutation $\pi$ as an even permutation $\bar{\pi}$, and show how to reformulate our sorting problems in terms of particular factorisations of the latter permutation. Using our framework, we recover known results in a simple and unified way, and obtain a new lower bound on the \emph{prefix transposition distance} (where a \emph{prefix transposition} displaces the initial segment of a permutation), which is shown to outperform previous results. Moreover, we use our approach to improve the best known lower bound on the \emph{prefix transposition diameter} from $2n/3$ to $\lfloor3n/4\rfloor$, and investigate a few relations between some statistics on $\pi$ and $\bar{\pi}$.

Let $k\ge 2$ be a positive integer, and let $d$ be a nonnegative integer. A graph $G$ is $d$-improperly $k$-choosable, or simply, $(k,d)$-choosable if, for every list assignment $L$ with $|L(v)|\geq k$ for every $v\in V (G)$, there exists an $L$-coloring of $G$ such that each vertex of $G$ has at most $d$ neighbors colored the same color as itself. It is known that every planar graph with cycles of length neither 4 nor $k$ for some $k\in\{5,6,7,8,9\}$ is $(3,1)$-choosable. In this paper, we prove that every planar graph without cycles of length 4 is $(3,1)$-choosable. This is best possible in the following two senses: (i) there are planar graphs which are not $(3,1)$-colorable, hence not $(3,1)$-choosable; (ii) there are planar graphs without 4-cycles which are not $(3,0)$-colorable, hence not $(3,0)$-choosable.

While the minimax (or maximin) strategy has become the standard and most agreed-upon solution for decision making in adversarial settings, as discussed in game theory, computer science, and other disciplines, its power arises from the use of mixed strategies, also known as probabilistic algorithms. Nevertheless, in adversarial settings we face the risk of information leakage about the actual strategy instantiation. Hence, real robust algorithms should take information leakage into account. In this paper we introduce the notion of adversarial leakage in games, namely, the ability of a player to learn the value of $b$ binary predicates about the strategy instantiation of her opponent. Different leakage models are suggested and tight bounds on the effect of adversarial leakage as a function of the level of leakage (captured by $b$) are established. The complexity of computing optimal strategies under these adversarial leakage models is also addressed. Together, our study introduces a new framework for robust...

A graph $G$ is called $(r,s)$-edge-choosable if for every assignment of sets of size $r$ to the edges of $G$ it is possible to choose for every edge an $s$-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph $G$ is the infimum of all numbers $r/s$ for which $G$ is $(r,s)$-edge-choosable. Mohar [http://www.fmf.uni-lj.si/$\sim$mohar/ (June 2003)] posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Math., 23 (2009), pp. 872--881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list f...

The classical Feedback Vertex Set problem asks, for a given undirected graph $G$ and an integer $k$, to find a set of at most $k$ vertices that hits all the cycles in the graph $G$. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (Subset-FVS), where an instance comes additionally with a set $S \subseteq V$ of vertices, and we ask for a set of at most $k$ vertices that hits all simple cycles passing through $S$. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225--267; SIAM J. Comput., 30 (2000), pp. 1231--1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed in...

The Gyarfas tree packing conjecture states that any set of $n-1$ trees $T_{1},T_{2},\dots, T_{n-1}$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ (for $n$ large enough). We show that $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_{n+1}$ (for $n$ large enough). We also prove that any set of $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices packs into $K_{n}$ (for $n$ large enough). Finally, we prove that $t=\frac{1}{4}n^{1/3}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ as long as each tree has maximum degree at least $2n^{2/3}$ (for $n$ large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlos, Sarkozy, and Szemeredi [Combin. Probab. Comput., 10 (2001), pp. 397--416].

In this paper we introduce digital nets over finite abelian groups which contain digital nets over finite fields and certain rings as a special case. We prove a MacWilliams type identity for such digital nets. This identity can be used to compute the strict $t$-value of a digital net over finite abelian groups. If the digital net has $N$ points in the $s$ dimensional unit cube $[0,1]^s$, then the $t$-value can be computed in $\mathcal{O}(N s \log N)$ operations and the weight enumerator polynomial can be computed in $\mathcal{O}(N s (\log N)^2)$ operations, where operations mean arithmetic of integers. By precomputing some values the number of operations of computing the weight enumerator polynomial can be reduced further.

Following the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we study the category ${\cal U}{\cal B} igr_n$ of loop-free edge-bipartite (signed) graphs $\Delta$, with $n\geq 2$ vertices, up to $\mathbb{Z}$-congruences $\sim_\mathbb{Z}$ and $\approx_\mathbb{Z}$ (defined in the paper), by means of the Gram matrix $ \check G_\Delta \in \mathbb{M}_n(\mathbb{Z})$, the Coxeter--Gram matrix ${\rm Cox}_\Delta= - \check G_\Delta\cdot \check G_\Delta^{-tr} \in \mathbb{M}_n(\mathbb{Z})$, the spectrum $ {\bf specc}_\Delta$ of $\mbox{\rm Cox}_\Delta$, the Coxeter polynomial $\mbox{\rm cox}_\Delta(t)\in \mathbb{Z}[t]$, the Coxeter number ${\bf c}_\Delta \geq 2$, and the $\mathbb{Z}$-bilinear Gram form $b_\Delta: \mathbb{Z}^n\times \mathbb{Z}^n \to \mathbb{Z}$ of $\Delta$. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. One of our aims is to compute the set ${\cal C}{\cal G} p...

In a weighted independence system, an independent set is said to be $\alpha$-robust if, for all $p$, the total weight of its heaviest $p$ elements is at least $\alpha$ times the maximum weight of a $p$-independent set. Here a $p$-independent set is an independent set with at most $p$ elements. The set of matchings in a weighted graph is a typical example of a weighted independence system, and Hassin and Rubinstein [SIAM J. Discrete Math., 15 (2002), pp. 530--537] showed that every graph has a $\frac{1}{\sqrt2}$-robust matching and it can be found by a $k$th power algorithm in polynomial time. In this paper, we show that it can be extended to the matroid intersection problem; i.e., there always exists a $\frac{1}{\sqrt2}$-robust matroid intersection, which is polynomially computable. We also study the time complexity of the robust matching problem. We show that a 1-robust matching can be computed in polynomial time (if one exists), and, for any fixed number $\alpha$ with $\frac{1}{\sqrt2}

A unique-path labeling of a simple, finite graph is a labeling of its edges with real numbers such that for every ordered pair of vertices $(u,v)$, there is at most one nondecreasing path from $u$ to $v$. In this paper we prove that any graph on $n$ vertices that admits a unique-path labeling has at most $n \log_2(n)/2$ edges and that this bound is tight for infinitely many values of $n$. Thus we significantly improve on the previously best known bounds. The main tool of the proof is a combinatorial lemma which might be of independent interest. For every $n$ we also construct an $n$-vertex graph that admits a unique-path labeling and has $n\log_2(n)/2 - O(n)$ edges.

Given a directed simple graph $G=(V,E)$ and a cost function $c:E \rightarrow R_+$, the power of a vertex $u$ in a directed spanning subgraph $H$ is given by $p_H(u) = \max_{uv \in E(H)} c(uv)$, and corresponds to the energy consumption required for wireless node $u$ to transmit to all nodes $v$ with $uv \in E(H)$. The power of $H$ is given by $p(H) = \sum_{u \in V} p_H(u)$. Power Assignment seeks to minimize $p(H)$ while $H$ satisfies some connectivity constraint. In this paper, we assume $E$ is bidirected (for every directed edge $e \in E$, the opposite edge exists and has the same cost), while $H$ is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that a bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In 2010, we introduced a greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the algorithm's analysis to 1.85, combining techniques from Robins and Zelikovsky in 20...

The concept of neighbor system, introduced by Hartvigsen in 2010, is a set of integral vectors satisfying a certain combinatorial property. In this paper, we reveal the relationship of neighbor systems with jump systems and with bisubmodular polyhedra. We first prove that for every neighbor system, there exists a jump system which has the same neighborhood structure as the original neighbor system. This shows that the concept of neighbor system is essentially equivalent to that of jump system. We next show that the convex closure of a neighbor system is an integral bisubmodular polyhedron. In addition, we give a characterization of neighbor systems using bisubmodular polyhedra. Finally, we consider the problem of minimizing a separable convex function on a neighbor system. It is shown that the problem can be solved in weakly polynomial time for a class of neighbor systems.

Let $G=(V,E)$ be a graph. A set $S\subseteq V$ is independent if no two vertices from $S$ are adjacent, while $\mathrm{core}(G)$ is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149-161]. The independence number $\alpha(G)$ is the cardinality of a largest independent set, and $\mu(G)$ is the size of a maximum matching of $G$. The neighborhood of $A\subseteq V$ is $\mathcal{N}(A)=\{v\in V:\mathcal{N}(v)\cap A\neq\emptyset\}$. The number $d_{c}(G)=\max\{\vert X\vert -\vert \mathcal{N}(X)\vert :X\subseteq V\}$ is called the critical difference of $G$, and $A$ is critical if $\vert A\vert -\vert \mathcal{N}% (A)\vert =d_{c}(G)$ [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431-438]. We define $\mathrm{\ker}(G)$ as the intersection of all critical sets. In this paper we prove that if $d_{c}(G)\geq1$, then $\mathrm{\ker}(G)\subseteq\mathrm{core}(G)$ and $\vert \mathrm{\ker}(G)\vert >d_{c}(G) \geq\alpha(G) -\mu(G)$.