45 papers
This paper establishes that for hypergraphs derived from cross-free connected subgraphs of a bounded-genus host graph, there exists a support graph that also maintains bounded genus, thereby generalizing prior planar results and providing a unified framework for solving packing, covering, and coloring problems on surfaces.
This paper investigates the WELLDOC property, an abelian-type characteristic of infinite words concerning the distribution of Parikh vectors of prefixes, and establishes a criterion for determining whether words generated by morphisms possess this property.
This paper presents a concise and self-contained proof of Delahan's theorem, demonstrating that every simple graph with vertices appears as an induced subgraph of a Steinhaus graph with vertices by utilizing the concept of generating index sets for Steinhaus triangles.
This paper provides a complete characterization of interval nest digraphs by introducing "nest orderings," a specific type of vertex linear ordering defined by forbidden patterns, thereby completing the set of vertex-ordering characterizations for major subclasses of interval digraphs.
This paper derives explicit formulas for general position polynomials of complete multipartite graphs and investigates their unimodality and log-concavity, demonstrating that these properties hold for balanced complete multipartite graphs with small part sizes and for coronas of various graph classes, while failing for larger part sizes.
This paper develops quantitative tools to study random minimum spanning trees (MST) generated by assigning independent random weights to edges, extending beyond the standard uniform distribution to more general product measures.
This paper investigates the properties of the linear chromatic number, a graph parameter introduced by Kun et al. as a relaxation of treedepth, and establishes improved bounds for this parameter across several graph classes.
This paper presents a generalized matrix-tree theorem that accommodates non-zero column sums by introducing a root vertex, uses this result to prove an all-minors matrix-forest theorem, and demonstrates applications in modeling discrete state time-evolution and computing determinants.
This paper develops explicit and compact formulas for the M-polynomial of seven specific graph products (direct, Cartesian, strong, lexicographic, symmetric-difference, disjunction, and Sierpiński), thereby providing a unified framework to describe how vertex-degree interactions propagate under these constructions and extending existing results for degree-based topological indices.
This paper provides the first complete proof of a closed formula involving Beatty-type bracket expressions for determining the P-positions and full nim-value structure of additive subtraction games in the primitive quadratic regime, resolving a long-standing open problem from *Winning Ways*.
This paper establishes the threshold probability for a random collection of -subsets to form a matroid, proves that such random matroids are typically sparse paving, and utilizes these findings to improve asymptotic estimates for the total number of matroids of rank on elements, particularly when grows with .
This paper presents a fixed-parameter tractable algorithm that resolves the open question of whether a graph can be covered by fewer than vertex-disjoint paths by outputting either a minimum path cover or an independent set certifying the cover's near-optimality, while also providing the first polynomial-time Hamiltonian path decision for graphs with independence number at most three.
This paper introduces block-separated overpartitions, a constrained family where no two consecutive distinct part-blocks are both overlined, and demonstrates that their enumeration is governed by Fibonacci-type combinatorics, leading to a rich algebraic structure including Euler products and recurrence relations, while sharing the same exponential growth rate as ordinary partitions.
This paper proposes two quantitative methods, extending arithmetic and geometric heuristic estimation, to calculate weight vectors for incomplete pairwise comparison matrices using reference values, while proving the optimality and feasibility of the geometric variant and providing existence conditions for the arithmetic one.
This paper investigates the complexity of the Distance- Dominating Set Reconfiguration problem for under Token Jumping and Token Sliding rules, establishing a PSPACE-complete to P complexity dichotomy on split graphs, providing a linear-time algorithm for trees, and extending hardness results to planar graphs with maximum degree three and various other graph classes.
This paper establishes that the reversibility of any first-degree cellular automaton over for arbitrary lattice sizes can be determined in constant time by verifying three specific algebraic conditions on its eight defining parameters, thereby enabling the efficient synthesis and identification of all such reversible rules.
This paper investigates the structural properties of shortest flip sequences between plane spanning trees on point sets in convex position, confirming the validity of the "parking edge" and "reparking" conjectures in specific cases while disproving them in the general setting.
This paper presents the first approximation algorithms for two generalizations of the Maximum Quadratic Assignment Problem—Maximum List-Restricted Quadratic Assignment and Maximum Quadratic -Matching Assignment—achieving and approximation factors respectively, which asymptotically match the best known bounds for the standard MaxQAP under specific conditions.
This paper investigates the parameterized complexity of the NP-complete Shortest Path problem with positive disjunctive constraints, establishing fixed-parameter tractability and providing polynomial kernelizations of size and based on the solution size and specific structural properties of the forcing graph.
This paper resolves the open question regarding the parameterized complexity of the Optimal Morse Matching problem by presenting a $2^{O(k \log k)} n$-time algorithm for bounded-treewidth complexes and proving its optimality under the Exponential Time Hypothesis.