Search

Nakajima's graded quiver varieties naturally appear in the study of bases of cluster algebras. One particular family of these varieties, namely the bipartite determinantal varieties, can be defined for any bipartite quiver and gives a vast generalization of classical determinantal varieties with broad applications to algebra, geometry, combinatorics, and statistics. The ideals that define bipartite determinantal varieties are called bipartite determinantal ideals. We provide an elementary method of proof showing that the natural generators of a bipartite determinantal ideal form a Gröbner basis, using an S-polynomial construction method that relies on the Leibniz formula for determinants. This method is developed from an idea by Narasimhan and Caniglia–Guccione–Guccione. As applications, we study the connection between double determinantal ideals (which are bipartite determinantal ideals of a quiver with two vertices) and tensors, and provide an interpretation of these ideals within the context of algebraic statistics. [ABSTRACT FROM AUTHOR]

Let (X,\tau) be a Polish space with Borel probability measure \mu, and G a locally finite one-ended Borel graph on X. We show that G admits a Borel one-ended spanning tree generically. If G is induced by a free Borel action of an amenable (resp., polynomial growth) group then we show the same result \mu-a.e. (resp., everywhere). Our results generalize recent work of Timár, as well as of Conley, Gaboriau, Marks, and Tucker-Drob, who proved this in the probability measure preserving setting. We apply our theorem to find Borel orientations in even-degree graphs and measurable and Baire measurable perfect matchings in regular bipartite graphs, refining theorems that were previously only known to hold for measure preserving graphs. In particular, we prove that bipartite one-ended d-regular Borel graphs admit Baire measurable perfect matchings. [ABSTRACT FROM AUTHOR]

In matching theory, one of the most fundamental and classical branches of combinatorics, canonical decompositions of graphs are powerful and versatile tools that form the basis of this theory. However, the abilities of the known canonical decompositions, that is, the Dulmage–Mendelsohn, Kotzig–Lovász, and Gallai–Edmonds decompositions, are limited because they are only applicable to particular classes of graphs, such as bipartite graphs, or they are too sparse to provide sufficient information. To overcome these limitations, we introduce a new canonical decomposition that is applicable to all graphs and provides much finer information. This decomposition also provides the answer to the longstanding absence of a canonical decomposition that is nontrivially applicable to general graphs with perfect matchings. We focus on the notion of factor‐components as the fundamental building blocks of a graph; through the factor‐components, our new canonical decomposition states how a graph is organized and how it contains all the maximum matchings. The main results that constitute our new theory are the following: (i) a canonical partial order over the set of factor‐components, which describes how a graph is constructed from its factor‐components; (ii) a generalization of the Kotzig–Lovász decomposition, which shows the inner structure of each factor‐component in the context of the entire graph; and (iii) a canonically described interrelationship between (i) and (ii), which integrates these two results into a unified theory of a canonical decomposition. These results are obtained in a self‐contained way, and our proof of the generalized Kotzig–Lovász decomposition contains a shortened and self‐contained proof of the classical counterpart. [ABSTRACT FROM AUTHOR]

In this paper, we calculate the expected values of the first and second Zagreb indices, denoted as E(M1) and E(M2) respectively, as well as the expected value of the forgotten index, E(F), for two models of random bipartite graphs. To evaluate our findings, we establish the growth rate by demonstrating that for a random bipartite graph G of order n in either model, the expected value of M1(G) is O(n³). Furthermore, we prove that the expected values of M2(G) and F(G) are both O(n4). [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

We construct explicit combinatorial Bernoulli factories for the following class of flowbased polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and k-flows. In the process, we uncover new connections to algebraic combinatorics. [ABSTRACT FROM AUTHOR]

We introduce a family of spaces called critical varieties. Each critical variety is a subset of one of the positroid varieties in the Grassmannian. The combinatorics of positroid varieties is captured by the dimer model on a planar bipartite graph G, and the critical variety is obtained by restricting to Kenyon's critical dimer model associated to a family of isoradial embeddings of G. This model is invariant under square/spider moves on G, and we give an explicit boundary measurement formula for critical varieties which does not depend on the choice of G. This extends our recent results for the critical Ising model, and simultaneously also includes the case of critical electrical networks. We systematically develop the basic properties of critical varieties. In particular, we study their real and totally positive parts, the combinatorics of the associated strand diagrams, and introduce a shift map motivated by the connection to zonotopal tilings and scattering amplitudes. [ABSTRACT FROM AUTHOR]

We characterize the completely determined Borel subsets of HYP as exactly the Δ 1 (L ω 1 c k ) subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author. [ABSTRACT FROM AUTHOR]

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable. [ABSTRACT FROM AUTHOR]

A graph is called equimatchable if all of its maximal matchings have the same size. Lesk et al. [Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254] has provided a characterization of equimatchable bipartite graphs. Motivated by the fact that this characterization is not structural, Frendrup et al. [A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190] has also provided a structural characterization for equimatchable graphs with girth at least five, in particular, a characterization for equimatchable bipartite graphs with girth at least six. In this paper, we extend the characterization of Frendrup by eliminating the girth condition. For an equimatchable graph, an edge is said to be a critical-edge if the graph obtained by the removal of this edge is not equimatchable. An equimatchable graph is called edge-critical, denoted by ECE, if every edge is critical. Noting that each ECE-graph can be obtained from some equimatchable graph by recursively removing non-critical edges, each equimatchable graph can also be constructed from some ECE-graph by joining some non-adjacent vertices. Our study reduces the characterization of equimatchable bipartite graphs to the characterization of bipartite ECE-graphs. [ABSTRACT FROM AUTHOR]

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of the search trees on G, defined recursively by a root r together with search trees on each of the connected components of G - r . In particular, the 1-skeleton of the corresponding graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. We give a tight bound of Θ (m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. We also prove that the maximum diameter of associahedra of graphs of pathwidth two is Θ (n log n) . Finally, we give the exact diameter of the associahedra of complete split graphs and of unbalanced complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Arc-Disjoint Cycle Packing is a classical NP -complete problem and we study it from two perspectives: (1) by restricting the cycles in the packing to be of a fixed length, and (2) by restricting the inputs to bipartite tournaments. Focusing first on Arc-Disjoint r -Cycle Packing (where the cycles in the packing are required to be of length r), we show NP -completeness in oriented graphs with girth r for each r ≥ 3 and study the parameterized complexity of the problem with respect to two parameterizations (solution size and vertex cover size) for r = 4 in oriented graphs. Moving on to Arc-Disjoint Cycle Packing in bipartite tournaments, we show that every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7 (k − 1). This result adds to the set of Erdös-Pósa-type results known in the combinatorics literature for packing and covering problems. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced bipartite digraph on 2a vertices. For x , y , z ∈ V (D) , if x → z and y → z , then we call the pair { x , y } dominating; if z → x and z → y , then we call the pair { x , y } dominated. In 2017, Adamus [Graphs and Combinatorics, 33(2017) 43–51] proved that if d (x) + d (y) ≥ 3 a whenever { x , y } is a dominating or dominated pair, then D is Hamiltonian. In 2021, Adamus [Discrete Mathematics, 344(3) (2021) 112240] proved that if only every dominating pair of vertices { x , y } in D satisfies d (x) + d (y) ≥ 3 a + 1 , then D is Hamiltonian. In this paper, we show that the same conclusion is reached if we replace 3 a + 1 with 3a in the above condition. The lower bound for 3a is sharp. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G = (V 1 , V 2 , E) , a biclique of G is a complete bipartite subgraph of G , and a biclique partitioning of G is a set A ⊆ E such that the bipartite graph G ′ = (V 1 , V 2 , A) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = (V 1 , V 2 , E) with edge weights w e ∈ R for all e ∈ E (thus, negative weights are allowed), finding a biclique partitioning A ⊆ E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P n m of the complete bipartite graph K n m (i.e., P n m is the convex hull of the incidence vectors of the biclique partitionings of K n m). In this paper we develop such a polyhedral study and show that ladder , bellows , and grid inequalities induce facets of P n m. Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%. [ABSTRACT FROM AUTHOR]

Let $\gamma(G)$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n-vertex graph of minimum degree at least d, then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n-vertex d-regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d. This result is sharp in the sense that as $d \rightarrow \infty$ , almost all d-regular n-vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of ${n}/{(2d)}$ complete bipartite graphs $K_{d,d}$ , then ${\gamma_\circ}(G) = \frac{n}{2}$. We also prove that there are n-vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that ${\gamma_\circ}(G) \sim {n}/{2}$ as $d \rightarrow \infty$. Therefore both the girth and regularity conditions are required for the main result. [ABSTRACT FROM AUTHOR]

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal. We specifically study graphs that have an ordering avoiding some ordered structures. More precisely, we consider structures that we call patterns on three nodes, and we study the complexity of recognizing the classes associated with such patterns. In this domain, there are three key previous works. Independently Skrien [J. Graph Theory, 6 (1982), pp. 309-316] and Damashke [Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 219--229] noted that several graph classes, such as chordal, bipartite, interval, and comparability graphs, have a characterization in terms of forbidden patterns. On the algorithmic side, Hell, Mohar, and Rafiey [Ordering without forbidden patterns, in Algorithms--ESA 2014, Springer, 2014, pp. 554--565] proved that any class defined by a set of forbidden patterns on three nodes can be recognized in time O(n3) by using an algorithm based on an extension of 2-SAT. We improve on these two lines of works by systematically characterizing all the classes defined by sets of forbidden patterns (on three nodes) and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time. Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating. [ABSTRACT FROM AUTHOR]

A bipartite graph $H = \left (V_1, V_2; E \right)$ with $\lvert V_1\rvert + \lvert V_2\rvert = n$ is semilinear if $V_i \subseteq \mathbb {R}^{d_i}$ for some $d_i$ and the edge relation E consists of the pairs of points $(x_1, x_2) \in V_1 \times V_2$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $d_1 + d_2$ variables for some s. We show that for a fixed k, the number of edges in a $K_{k,k}$ -free semilinear H is almost linear in n, namely $\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right)$ for any $\varepsilon> 0$ ; and more generally, $\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right)$ for a $K_{k, \dotsc ,k}$ -free semilinear r-partite r-uniform hypergraph. As an application, we obtain the following incidence bound: given $n_1$ points and $n_2$ open boxes with axis-parallel sides in $\mathbb {R}^d$ such that their incidence graph is $K_{k,k}$ -free, there can be at most $O_{k,\varepsilon }\left (n^{1+\varepsilon }\right)$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o-minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner). [ABSTRACT FROM AUTHOR]

Consider the following hat guessing game: n players are placed on n vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. Given a graph G , its hat guessing number HG (G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors. In 2008, Butler et al. asked whether the hat guessing number of the complete bipartite graph K n , n is at least some fixed positive (fractional) power of n. We answer this question affirmatively, showing that for sufficiently large n , the complete r -partite graph K n , ... , n satisfies HG (K n , ... , n) = Ω (n r − 1 r − o (1)). Our guessing strategy is based on a probabilistic construction and other combinatorial ideas, and can be extended to show that HG ( C → n , ... , n) = Ω (n 1 r − o (1)) , where C → n , ... , n is the blow-up of a directed r -cycle, and where for directed graphs each player sees only the hat colors of his outneighbors. Additionally, we consider related problems like the relation between the hat guessing number and other graph parameters, and the linear hat guessing number, where the players are only allowed to use affine linear guessing strategies. Several nonexistence results are obtained by using well-known combinatorial tools, including the Lovász Local Lemma and the Combinatorial Nullstellensatz. Among other results, it is shown that under certain conditions, the linear hat guessing number of K n , n is at most 3, exhibiting a huge gap from the Ω (n 1 2 − o (1)) (nonlinear) hat guessing number of this graph. [ABSTRACT FROM AUTHOR]

A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k -partition exists is known as the total domatic number of a graph G , denoted by d t (G). We extend considerably the known hardness results by showing it is Image 1 -complete to decide whether d t (G) ≥ 3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k ≥ 3 , it is Image 1 -complete to decide whether d t (G) ≥ k , where G is split or k -regular. In particular, these results complement recent combinatorial results regarding d t (G) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n -vertex graphs, we show the problem is solvable in 2 n n O (1) time, and derive even faster algorithms for special graph classes. [ABSTRACT FROM AUTHOR]

We study the relationship between hyperfiniteness and problems in Borel graph combinatorics by adapting game-theoretic techniques introduced by Marks to the hyperfinite setting. We compute the possible Borel chromatic numbers and edge chromatic numbers of bounded degree acyclic hyperfinite Borel graphs and use this to answer a question of Kechris and Marks about the relationship between Borel chromatic number and measure chromatic number. We also show that for every d > 1 there is a d-regular acyclic hyperfinite Borel bipartite graph with no Borel perfect matching. These techniques also give examples of hyperfinite bounded degree Borel graphs for which the Borel local lemma fails, in contrast to the recent results of Cs'oka, Grabowski, M'ath'e, Pikhurko, and Tyros. Related to the Borel Ruziewicz problem, we show there is a continuous paradoxical action of (Z/2Z)*3 on a Polish space that admits a finitely additive invariant Borel probability measure, but admits no countably additive invariant Borel probability measure. In the context of studying ultrafilters on the quotient space of equivalence relations under AD, we also construct an ultrafilter U on the quotient of E0 which has surprising complexity. In particular, Martin's measure is Rudin-Keisler reducible to U. We end with a problem about whether every hyperfinite bounded degree Borel graph has a witness to its hyperfiniteness which is uniformly bounded below in size. [ABSTRACT FROM AUTHOR]

We provide a deterministic algorithm that finds, in ɛ−O(1) n2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ−O(1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛn v(H), in time ɛ−OH(1)n2. [ABSTRACT FROM AUTHOR]

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Jackson and Yoshimoto showed that if G is a 3-edge-connected graph with ∣G∣ ≥ 5 and v is a vertex with degree 3, then G has an even factor F containing two given edges incident with v in which each component has order at least 5. We prove that this theorem is satisfied for each pair of adjacent edges. Also, we show that each 3-edge-connected graph has an even factor F containing two given edges e and f such that every component containing neither e nor f has order at least 5. But we construct infinitely many 3-edge-connected graphs that do not have an even factor F containing two arbitrary prescribed edges in which each component has order at least 5. [ABSTRACT FROM AUTHOR]

Abstract We give exact growth rates for the number of bipartite graceful permutations of the symbols { 0 , 1 , ... , n − 1 } that start with a for a ≤ 14 (equivalently, α -labelings of paths with n vertices that have a as a pendant label). In particular, when a = 14 the growth is asymptotically like λ n for λ ≈ 3. 461. The number of graceful permutations of length n grows at least this fast, improving on the best existing asymptotic lower bound of 2. 3 7 n. Combined with existing theory, this improves the known lower bounds on the number of Hamiltonian decompositions of the complete graph K 2 n + 1 and on the number of cyclic oriented triangular embeddings of K 12 s + 3 and K 12 s + 7. We also give the first exponential lower bound on the number of R-sequencings of Z 2 n + 1. [ABSTRACT FROM AUTHOR]

We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues. [ABSTRACT FROM AUTHOR]

We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues. [ABSTRACT FROM AUTHOR]

Given a collection τ of subsets of a finite set X, we say that τ is phylogenetically flexible if, for any collection R of rooted phylogenetic trees whose leaf sets comprise the collection τ, R is compatible (i.e. there is a rooted phylogenetic X-tree that displays each tree in R). We show that τ is phylogenetically flexible if and only if it satisfies a Hall-type inequality condition of being 'slim'. Using submodularity arguments, we show that there is a polynomial-time algorithm for determining whether or not τ is slim. This 'slim' condition reduces to a simpler inequality in the case where all of the sets in τ have size 3, a property we call 'thin'. Thin sets were recently shown to be equivalent to the existence of an (unrooted) tree for which the median function provides an injective mapping to its vertex set; we show here that the unrooted tree in this representation can always be chosen to be a caterpillar tree. We also characterise when a collection τ of subsets of size 2 is thin (in terms of the flexibility of total orders rather than phylogenies) and show that this holds if and only if an associated bipartite graph is a forest. The significance of our results for phylogenetics is in providing precise and efficiently verifiable conditions under which supertree methods that require consistent inputs of trees can be applied to any input trees on given subsets of species. [ABSTRACT FROM AUTHOR]

Abstract An expression of the coefficient of immanantal polynomial of an n × n matrix is present. Moreover, we give expressions of the coefficient of immanantal polynomials of combinatorial matrices (adjacency matrix, Laplacian matrix, signless Laplacian matrix). As applications, we show that the immanantal polynomials for Laplacian matrix and signless Laplacian matrix of bipartite graphs are the same. This is a generalization of the characteristic polynomial for Laplacian matrix and signless Laplacian matrix of bipartite graphs. Furthermore, we consider the relations between the characteristic polynomial and the immanantal polynomial for trees. [ABSTRACT FROM AUTHOR]

This paper defines the related notions of bipartite and Eulerian minors for binary matroids. Using these definitions, it characterizes graphic matroids within the classes of bipartite binary matroids and Eulerian binary matroids by the exclusion of certain bipartite minors and Eulerian minors, respectively. This result on Eulerian minors in binary matroids extends a result of Chudnovsky et al. who characterized planar graphs within the class of bipartite graphs by the exclusion of K 3 , 3 as a bipartite minor. [ABSTRACT FROM AUTHOR]

The well known 1–2–3-Conjecture asserts that every connected graph G with at least three vertices can be edge weighted with 1 , 2 , 3 , so that for any two adjacent vertices u and v , the sum of the weights of the edges incident to u is distinct from the sum of the weights of the edges incident to v . In this paper, we consider the list version of this problem and prove that graphs with maximum average degree smaller than 11 4 are strongly ( 1 , 3 ) -choosable, which implies that the 1–2–3 conjecture is true for such graphs. This improves the results in Cranston et al. (2014)[7] and Przybyło et al. (2017). [ABSTRACT FROM AUTHOR]

It is a classical result that an unrooted tree T having positive real-valued edge lengths and no vertices of degree two can be reconstructed from the induced distance between each pair of leaves. Moreover, if each non-leaf vertex of T has degree 3 then the number of distance values required is linear in the number of leaves. A canonical candidate for such a set of pairs of leaves in T is the following: for each non-leaf vertex v , choose a leaf in each of the three components of T − v , group these three leaves into three pairs, and take the union of this set over all choices of v . This forms a so-called ‘triplet cover’ for T . In the first part of this paper we answer an open question (from 2012) by showing that the induced leaf-to-leaf distances for any triplet cover for T uniquely determine T and its edge lengths. We then investigate the finer combinatorial properties of triplet covers. In particular, we describe the structure of triplet covers that satisfy one or more of the following properties of being minimal, ‘sparse’, and ‘shellable’. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems, in which the defective objects are replaced by the judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that the simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes. [ABSTRACT FROM AUTHOR]

We show that the inequality H(A | B,X) + H(A | B,Y) \leqslant H(A | B) for jointly distributed random variables A,B,X,Y , which does not hold in general case, holds under some natural condition on the support of the probability distribution of A,B,X,Y . This result generalizes a version of the conditional Ingleton inequality: if for some distribution , then I(A \mskip 5mu {:} \mskip 5mu B) \leqslant I(A \mskip 5mu {:} \mskip 5mu B | X) + I(A \mskip 5mu {:} \mskip 5mu B | Y) + I(X \mskip 5mu {:} \mskip 5mu Y) . We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K$ colors so that each two edges sharing a vertex have different colors and for each pair (left vertex $x$ , right vertex $y$ ) there is at most one color $a$ such both $x$ and $y$ are incident to edges with color $a$ ; assume further that the degree of each left vertex is at least $L$ and the degree of each right vertex is at least $R$ . Then $K \geqslant LR$ . The second application is a new method to prove lower bounds for biclique cover of bipartite graphs. [ABSTRACT FROM PUBLISHER]

We study the polynomial time approximation of the NP -hard max k - vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2 3 and 34 47 ≈ 0 . 72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio ( 1 − 1 e ) ≈ 0 . 632 . Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for max k - vertex cover compete with linear programming ones? [ABSTRACT FROM AUTHOR]

We propose and analyze a simple purely combinatorial algorithm for max k-vertex cover in bipartite graphs, achieving approximation ratio 0.7. The only combinatorial algorithm currently known until now for this problem is the natural greedy algorithm, that achieves ratio (e − 1)/e = 0.632. [ABSTRACT FROM AUTHOR]

A C k -free 2 -matching in an undirected graph is a simple 2 -matching which does not contain cycles of length k or less. The complexity of finding the maximum C k -free 2 -matching in a given graph varies depending on k and the type of input graph. The case where k = 4 and the graph is bipartite, which is called the maximum square-free 2 -matching problem in bipartite graphs, is well-solved. Previous results for this special case include min-max theorems, polynomial combinatorial algorithms, a linear programming formulation with dual integrality for a weighted version, and discrete convex structures. In this paper, we further investigate the structure of square-free 2 -matchings in bipartite graphs and present new decomposition theorems. These theorems serve as analogues of the Dulmage-Mendelsohn decomposition for matchings in bipartite graphs and the Edmonds-Gallai decomposition for matchings in nonbipartite graphs. We exhibit two canonical minimizers for the set function in the min-max formula, and a characterization of the maximum square-free 2 -matchings with the aid of these canonical minimizers. [ABSTRACT FROM AUTHOR]

A matroid M has all-graphic cocircuits if M ∖ Y is a graphic matroid for every cocircuit Y ∈ C ∗ ( M ) . In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in G F ( 2 ) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm. [ABSTRACT FROM AUTHOR]

We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle. [ABSTRACT FROM AUTHOR]

We consider combinatorial algorithms for the minimum-cost flow problem on networks with unit capacities, and special cases of the problem. Historically, researchers have developed special-purpose algorithms that exploit unit capacities. In contrast, for the maximum flow problem, the classical blocking flow and push-relabel algorithms for the general case also have the best bounds known for the special case of unit capacities. In this paper we show that the classical blocking flow push-relabel cost-scaling algorithms of Goldberg and Tarjan (Math. Oper. Res. 15, 430-466, 1990) for general minimum-cost flow problems achieve the best known bounds for unit-capacity problems as well. We also develop a cycle-canceling algorithm that extends Goldberg's shortest path algorithm (Goldberg SIAM J. Comput. 24, 494-504, 1995) to minimum-cost, unit-capacity flow problems. Finally, we combine our ideas to obtain an algorithm that solves the minimum-cost bipartite matching problem in $O(r^{1/2} m \log C)$ time, where m is the number of edges, C is the largest arc cost (assumed to be greater than 1), and r is the number of vertices on the small side of the vertex bipartition. This result generalizes (and simplifies) a result of Duan et al. (2011) and solves an open problem of Ramshaw and Tarjan (2012). [ABSTRACT FROM AUTHOR]

The problem of finding two radioactive balls among a given set of balls is reduced to a combinatorial recognition problem, and the latter is solved by a series of tests. Methods of graph theory are used to solve the problem. The approach is illustrated by an example with 22 balls. [ABSTRACT FROM AUTHOR]

The theory of combinatorial designs has recently been used in order to build switch-centric data centre networks incorporating a large number of servers, in comparison with the popular Fat-Tree data centre network. We clarify and extend these results and prove that in these data centre networks: there are pairwise link-disjoint paths joining all the servers adjacent to some switch with all the servers adjacent to any other switch; and there are pairwise link-disjoint paths from all the servers adjacent to some switch to any identically-sized collection of target servers where these target servers need not be adjacent to the same switch. In both cases, we always control the path lengths. Our constructions and analysis are undertaken on bipartite graphs with the applications to data centre networks being easily derived. Our results show the potential of the application of results and methodologies from combinatorics to data centre network design. [ABSTRACT FROM AUTHOR]

A restraint r on G is a function which assigns each vertex v of G a finite set of forbidden colours r ( v ) . A proper colouring c of G is said to be permitted by the restraint r if c ( v ) ∉ r ( v ) for every vertex v of G . A restraint r on a graph G with n vertices is called a k -restraint if ∣ r ( v ) ∣ = k and r ( v ) ⊆ { 1 , 2 , … , k n } for every vertex v of G . In this article we discuss the following problem: among all k -restraints r on G , which restraints permit the largest number of x -colourings for all large enough x ? We determine such extremal restraints for all bipartite graphs. [ABSTRACT FROM AUTHOR]

A connected graph G of even order v is called t -extendable if it contains a perfect matching, t < v / 2 and any matching of t edges is contained in some perfect matching. The extendability of G is the maximum t such that G is t -extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is 1 -extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions. In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter D ≥ 3 are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency k ≥ 3 that depend on k , λ and μ , where λ is the number of common neighbors of any two adjacent vertices and μ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency k grows linearly in k . We conjecture that the extendability of a distance-regular graph of even order and valency k is at least ⌈ k / 2 ⌉ − 1 and we prove this fact for bipartite distance-regular graphs. In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters. [ABSTRACT FROM AUTHOR]

Let S = ( a 1 , … , a m ; b 1 , … , b n ) be a pair of two nonincreasing sequences of positive integers, that is, a 1 , … , a m and b 1 , … , b n are two nonincreasing sequences of positive integers. The pair S = ( a 1 , … , a m ; b 1 , … , b n ) is said to be a bigraphic pair if there is a simple bipartite graph G = ( X ∪ Y , E ) such that a 1 , … , a m and b 1 , … , b n are the degrees of the vertices in X and Y , respectively. In this paper, we give a simple sufficient condition for a pair S = ( a 1 , … , a m ; b 1 , … , b n ) to be a bigraphic pair. The condition depends only on the lengths of two sequences of the pair and their largest and smallest elements. This result extends a result due to Alon et al. (2010). [ABSTRACT FROM AUTHOR]

Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system or to identify its weakest spots. Interdiction problems have been studied for a wide variety of classical combinatorial optimization problems. Most interdiction problems are NP-hard, and furthermore, even designing efficient approximation algorithms that allow for estimating the order of magnitude of a worst-case impact has turned out to be very difficult. Not very surprisingly, the few known approximation algorithms are heavily tailored for specific problems. Inspired by previous approaches to network flow interdiction we suggest a general method to obtain pseudoapproximations for many interdiction problems. More precisely, for any α > 0, our algorithm will return either a (1 + α)-approximation or a solution that may overrun the interdiction budget by a factor of at most 1 + 1/ α but is also at least as good as the optimal solution that respects the budget. Furthermore, our approach can handle submodular interdiction costs when the underlying problem is to find a maximum weight independent set in a matroid. Additionally, our approach can sometimes be refined by exploiting additional structural properties of the underlying optimization problem to obtain stronger results. We demonstrate this by presenting a polynomial-time approximation scheme for interdicting b-stable sets in bipartite graphs. [ABSTRACT FROM AUTHOR]

Given graphs T and H , the generalized Turán number ex (n , T , H) is the maximum number of copies of T in an n -vertex graph with no copies of H. Alon and Shikhelman, using a result of Erdős, determined the asymptotics of ex (n , K 3 , H) when the chromatic number of H is greater than three and proved several results when H is bipartite. We consider this problem when H has chromatic number three. Even this special case for the following relatively simple three chromatic graphs appears to be challenging. The suspension H ˆ of a graph H is the graph obtained from H by adding a new vertex adjacent to all vertices of H. We give new upper and lower bounds on ex (n , K 3 , H ˆ) when H is a path, even cycle, or complete bipartite graph. One of the main tools we use is the triangle removal lemma, but it is unclear if much stronger statements can be proved without using the removal lemma. [ABSTRACT FROM AUTHOR]