Search

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG(u, v), the k-slice Sk(u, v) contains all vertices x on a shortest uv-path such that dG(u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as,,interval thinness” and,,fellow traveler property”. Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS’21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses. [ABSTRACT FROM AUTHOR]

An edge e of a matching covered graph G is removable if G − e is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick G different from K4 and C6 has at least ∆ − 2 removable edges, where ∆ is the maximum degree of G. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between the modified Foata–Strehl action (a.k.a. valley-hopping)—a group action on permutations used to demonstrate the γ-positivity of the Eulerian polynomials—and the number of rixed points rix—a recursively-defined permutation statistic introduced by Lin in the context of an equidistribution problem. We give a linear-time iterative algorithm for computing the set of rixed points, and prove that the rix statistic is homomesic under valley-hopping. We also demonstrate that a bijection Φ introduced by Lin and Zeng in the study of the rix statistic sends orbits of the valley-hopping action to orbits of a cyclic version of valley-hopping, which implies that the number of fixed points fix is homomesic under cyclic valley-hopping. [ABSTRACT FROM AUTHOR]

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: Let D be a 2-strong digraph of order n ≥ 9. If n − 1 vertices of D have degrees at least n + k and the remaining vertex has degree at least n − k − 4, where k is a non-negative integer, then D is Hamiltonian. This is an extension of Ghouila-Houri’s theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for k = 0 there is a digraph of order n = 8 (respectively, n = 9) with the minimum degree n − 4 = 4 (respectively, with the minimum degree n − 5 = 4) whose n − 1 vertices have degrees at least n − 1, but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected. [ABSTRACT FROM AUTHOR]

A harmonious coloring of a k-uniform hypergraph H is a vertex coloring such that no two vertices in the same edge have the same color, and each k-element subset of colors appears on at most one edge. The harmonious number h(H) is the least number of colors needed for such a coloring. The paper contains a new proof of the upper bound h(H) = O( k√k k!m) on the harmonious number of hypergraphs of maximum degree ∆ with m edges. We use the local cut lemma of A. Bernshteyn. [ABSTRACT FROM AUTHOR]

A walk u0, u1, . . ., uk−1, uk in a graph G is a weakly toll walk if u0ui ∈ E(G) implies ui = u1 and ujuk ∈ E(G) implies uj = uk−1. A set S of vertices of G is weakly toll convex if for any two nonadjacent vertices x, y ∈ S, any vertex in a weakly toll walk between x and y is also in S. The weakly toll convexity is the graph convexity defined over weakly toll convex sets. If S and S \ {x} are convex sets, then x is an extreme vertex of S. A graph convexity is said to be a convex geometry if it satisfies the Minkowski-Krein-Milman property, which states that every convex set is the convex hull of its extreme vertices. It is known that chordal, Ptolemaic, weakly polarizable, and interval graphs can be characterized as convex geometries with respect to the monophonic, geodesic, m3 , and toll convexities, respectively. Inspired by previous results in (Alcón, Brešar, Gologranc, Gutierrez, Šumenjak, Peterin, and Tepeh, 2015), in this paper we prove that a graph is a convex geometry with respect to the weakly toll convexity if and only if it is a proper interval graph. Furthermore, some well-known graph invariants are studied with respect to the weakly toll convexity, namely the weakly toll number and the weakly toll hull number. In particular, we determine these invariants for trees and we find bounds for interval graphs. [ABSTRACT FROM AUTHOR]

Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class In(=, 6=,>) is the same as that of n - 1 - asc on the class In(>, 6=,=), which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on In(=, 6=,>) of asc and desc along with two other parameters, and do the same for n - 1 - asc and desc on In(>, 6=,=). By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result that the common cardinality of In(=, 6=,>) and In(>, 6=,=) is the same as that of Sn(4231, 42513). In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents. [ABSTRACT FROM AUTHOR]

A distributed graph algorithm is an algorithm where every node determines its output by inspecting its local neighborhood. As distributed environments are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much time. Unfortunately, most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs, or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. In this paper, we present several different perspectives for studying local certification: as a part of self-stabilizing algorithms, as a labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions. [ABSTRACT FROM AUTHOR]

We define a q-linear path in a hypergraph H as a sequence (e1,. . ., eL) of edges of H such that |ei nei+1| [[1, q]] and ei n ej = Ø if |i-j| > 1. In this paper, we study the connected components associated to these paths when q = k - 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph. [ABSTRACT FROM AUTHOR]

Given a set system (also well-known as a hypergraph) H = {U, X}, where U is a set of elements and X is a set of subsets of U, an exact hitting set S is a subset of U such that each subset in X contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as Exactly Hittable Interval Graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG. [ABSTRACT FROM AUTHOR]

Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components, and all graphs are considered 0-tough. The toughness of a graph is the largest t for which the graph is t-tough, whereby the toughness of complete graphs is defined as infinity. A graph is minimally t-tough if the toughness of the graph is t, and the deletion of any edge from the graph decreases the toughness. In this paper, we investigate the minimum degree and the recognizability of minimally t-tough graphs in the classes of chordal graphs, split graphs, claw-free graphs, and 2K2-free graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12. [ABSTRACT FROM AUTHOR]

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 +√5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words. [ABSTRACT FROM AUTHOR]

Mixed graphs have both directed and undirected edges. We consider mixed graphs that are regular in both directed and undirected degree and with given girth. Araujo-Pardo, Hern'andez-Cruz, andMontellano-Ballesteros recently established a lower bound for regular mixed graphs with directed degree one that generalizes the Moore bound. In this paper we show that, in at least one non-trivial case, their bound can be achieved. For a few other specific values of direct degree, undirected degree and girth we are able to identify graphs (mixed cages) of minimum possible order. We also obtain some fairly tight bounds for a few other cases. [ABSTRACT FROM AUTHOR]

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. [ABSTRACT FROM AUTHOR]

The analysis of strings of n random variables with geometric distribution has recently attracted renewed interest: Archibald et al. consider the number of distinct adjacent pairs in geometrically distributed words. They obtain the asymptotic (n → ∞) mean of this number in the cases of different and identical pairs. In this paper we are interested in all asymptotic moments in the identical case, in the asymptotic variance in the different case and in the asymptotic distribution in both cases. We use two approaches: the first one, the probabilistic approach, leads to variances in both cases and to some conjectures on all moments in the identical case and on the distribution in both cases. The second approach, the combinatorial one, relies on multivariate pattern matching techniques, yielding exact formulas for first and second moments. We use such tools as Mellin transforms, Analytic Combinatorics, Markov Chains. [ABSTRACT FROM AUTHOR]

An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow that reaches every vertex in V (D) from s while loosing exactly one unit of flow in each vertex other than s. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n -- 1, a network N admits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoint s-branchings. Thus, a classical result by Edmonds stating that a digraph contains k arc-disjoint s-branchings if and only if the in-degree of every set X ⊆ V (D) \ {s} is at least k also characterizes the existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger the capacities are, the closer an s-branching flow is from simply being an s-branching. This observation is further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomial algorithm to find the flows (if they exist) when every arc has capacity n -- c, for every fixed c ≥ 1, and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper, we investigate how a property that is a natural extension of the characterization by Edmonds' relates to the existence of k arc-disjoint s-branching flows in networks. Although this property is always necessary for the existence of the flows, we show that it is not always sufficient and that it is hard to decide if the desired flows exist even if we know beforehand that the network satisfies it. On the positive side, we show that it guarantees the existence of the desired flows in some particular cases depending on the choice of the capacity function or on the structure of the underlying graph of D, for example. We remark that, in those positive cases, polynomial time algorithms to find the flows can be extracted from the constructive proofs. [ABSTRACT FROM AUTHOR]

An edge-colored graph is rainbow if no two edges of the graph have the same color. An edge-colored graph Gc is called properly colored if every two adjacent edges of Gc receive distinct colors in Gc. A strongly edge-colored graph is a proper edge-colored graph such that every path of length 3 is rainbow. We call an edge-colored graph Gc rainbow vertex pair-pancyclic if any two vertices in Gc are contained in a rainbow cycle of length ℓ for each ℓ with 3 ≤ ℓ ≤ n. In this paper, we show that every strongly edge-colored graph Gc of order n with minimum degree δ ≤ 2n/3 + 1 is rainbow vertex pair-pancyclicity. [ABSTRACT FROM AUTHOR]

Gallai's path decomposition conjecture states that if G is a connected graph on n vertices, then the edges of G can be decomposed into at most [n/2] paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on 2k + 1 vertices by deleting at most k -- 1 edges. Bonamy and Perrett asked if the edges of every connected graph G on n vertices can be decomposed into at most [n/2] paths unless G is an odd semi-clique. A graph G is said to be 2-degenerate if every subgraph of G has a vertex of degree at most 2. In this paper, we prove that the edges of any connected 2-degenerate graph G on n vertices can be decomposed into at most [n/2] paths unless G is a triangle. [ABSTRACT FROM AUTHOR]

In 1946, Erdős posed the distinct distance problem, which seeks to find the minimum number of distinct distances between pairs of points selected from any configuration of n points in the plane. The problem has since been explored along with many variants, including ones that extend it into higher dimensions. Less studied but no less intriguing is Erdős' distinct angle problem, which seeks to find point configurations in the plane that minimize the number of distinct angles. In their recent paper "Distinct Angles in General Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolf use a logarithmic spiral to establish an upper bound of O(n²) on the minimum number of distinct angles in the plane in general position, which prohibits three points on any line or four on any circle. We consider the question of distinct angles in three dimensions and provide bounds on the minimum number of distinct angles in general position in this setting. We focus on pinned variants of the question, and we examine explicit constructions of point configurations in ℝ³ which use self-similarity to minimize the number of distinct angles. Furthermore, we study a variant of the distinct angles question regarding distinct angle chains and provide bounds on the minimum number of distinct chains in ℝ² and ℝ³. [ABSTRACT FROM AUTHOR]

This paper considers the following three Roman domination graph invariants on Kneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph Kn,k, we present exact values for Roman domination number γR(Kn,k) and total Roman domination number γR(Kn,k) proving that for n ≥ k(k + 1), γR(Kn,k) = γR(Kn,k) = 2(k + 1). For signed Roman domination number γR(Kn,k), the new lower and upper bounds for Kn,2 are provided: we prove that for n ≥ 12, the lower bound is equal to 2, while the upper bound depends on the parity of n and is equal to 3 if n is odd, and equal to 5 if n is even. For graphs of smaller dimensions, exact values are found by applying exact methods from literature. [ABSTRACT FROM AUTHOR]

The following problem has been known since the 80's. Let Γ be an Abelian group of order m (denoted |Γ| = m), and let t and mi, 1 ≤ i ≤ t, be positive integers such ∑i=1t mi = m -- 1. Determine when Γ* = Γ \ {0}, the set of non-zero elements of Γ, can be partitioned into disjoint subsets Si, 1 ≤ i ≤ t, such that |Si| = mi and ... s = 0 for every i 2 [1; t]. It is easy to check that mi ≥ 2 (for every i ∈ [1, t]) and |I(Γ)| ≠= 1 are necessary conditions for the existence of such partitions, where I(Γ) is the set of involutions of Γ. It was proved that the condition mi ≥ 2 is sufficient if and only if |I(Γ)} ∈ {0, 3} (see Zeng, (2015)). For other groups (i.e., for which |I(Γ)} ≠ 3 and |I(Γ)| > 1), only the case of any group Γ with Γ ≅ = (ℤ2)n for some positive integer n has been analyzed completely so far, and it was shown independently by several authors that mi ≥ 3 is sufficient in this case. Moreover, recently Cichacz and Tuza (2021) proved that, if |Γ| is large enough and |I(Γ)| > 1, then mi ≥ 4 is sufficient. In this paper we generalize this result for every Abelian group of order 2n. Namely, we show that the condition mi ≥ 3 is sufficient for Γ such that |I(Γ)} > 1 and |Γ| = 2n, for every positive integer n. We also present some applications of this result to graph magic- and anti-magic-type labelings. [ABSTRACT FROM AUTHOR]

In this paper we first study k × n Youden rectangles of small orders. We have enumerated all Youden rectangles for a range of small parameter values, excluding the almost square cases where k = n -- 1, in a large scale computer search. In particular, we verify the previous counts for (n, k) = (7, 3), (7, 4), and extend this to the cases (11, 5), (11, 6), (13, 4) and (21, 5). For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call near Youden rectangles. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above. [ABSTRACT FROM AUTHOR]

After fixing a canonical ordering (or labeling) of the elements of a finite poset, one can associate each linear extension of the poset with a permutation. Some recent papers consider specific families of posets and ask how many linear extensions give rise to permutations that avoid certain patterns. We build off of two of these papers. We first consider pattern avoidance in k-ary heaps, where we obtain a general result that proves a conjecture of Levin, Pudwell, Riehl, and Sandberg in a special case. We then prove some conjectures that Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding linear extensions of rectangular posets. [ABSTRACT FROM AUTHOR]

We consider the constrained graph alignment problem which has applications in biological network analysis. Given two input graphs G1 = (V1; E1), G2 = (V2, E2), two vertices u1, v1 of G1 paired respectively to two vertices u2, v2 of G2 induce an edge conservation if u1, v1 and u2, v2 are adjacent in their respective graphs. The goal is to provide a one-to-one mapping between some vertices of the input graphs in order to maximize edge conservation. However the allowed mappings are restricted since each vertex from V1 (resp. V2) is allowed to be mapped to at most m1 (resp. m²) specified vertices in V2 (resp. V1). Most of the results in this paper deal with the case m² = 1 which attracted most attention in the related literature. We formulate the problem as a maximum independent set problem in a related conflict graph and investigate structural properties of this graph in terms of forbidden subgraphs. We are interested, in particular, in excluding certain wheels, fans, cliques or claws (all terms are defined in the paper), which in turn corresponds to excluding certain cycles, paths, cliques or independent sets in the neighborhood of each vertex. Then, we investigate algorithmic consequences of some of these properties, which illustrates the potential of this approach and raises new horizons for further works. In particular this approach allows us to reinterpret a known polynomial case in terms of conflict graph and to improve known approximation and fixed-parameter tractability results through efficiently solving the maximum independent set problem in conflict graphs. Some of our new approximation results involve approximation ratios that are functions of the optimal value, in particular its square root; this kind of results cannot be achieved for maximum independent set in general graphs. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E) with a nonnegative edge length function and an integer p, 0 < p < |V |, the p-centdian problem is to find p vertices (called the centdian set) of V such that the eccentricity plus median-distance is minimized, in which the eccentricity is the maximum (length) distance of all vertices to their nearest centdian set and the median-distance is the total (length) distance of all vertices to their nearest centdian set. The eccentricity plus median-distance is called the centdian-distance. The purpose of the p-centdian problem is to find p open facilities (servers) which satisfy the quality-of-service of the minimum total distance (median-distance) and the maximum distance (eccentricity) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the centdian-distance and the objective function is to minimize the cardinality of the centdian set, this problem is called the converse centdian problem. In this paper, we prove the p-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the p-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems. [ABSTRACT FROM AUTHOR]

The average distance of a vertex v of a connected graph G is the arithmetic mean of the distances from v to all other vertices of G. The proximity π(G) and the remoteness ρ(G) of G are the minimum and the maximum of the average distances of the vertices of G, respectively. In this paper, we give upper bounds on the remoteness and proximity for graphs of given order, minimum degree and maximum degree. Our bounds are sharp apart from an additive constant. [ABSTRACT FROM AUTHOR]

We study the following problem. Given a multiset M of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to M. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds, independently of the magnitude of numbers belonging to the multisets. Our heuristic can also be used for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab. [ABSTRACT FROM AUTHOR]

Motivated by the study of pattern avoidance in the context of permutations and ordered partitions, we consider the enumeration of weak-ordering chains obtained as leaves of certain restricted rooted trees. A tree of order n is generated by inserting a new variable into each node at every step. A node becomes a leaf either after n steps or when a certain stopping condition is met. In this paper we focus on conditions of size 2 (x = y, x < y, or x y) and several conditions of size 3. Some of the cases considered here lead to the study of descent statistics of certain 'almost' pattern-avoiding permutations. [ABSTRACT FROM AUTHOR]

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K°urka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension 1, but also dimension 1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension. [ABSTRACT FROM AUTHOR]

Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. In particular, the layered treewidth of a graph G is the minimum integer k such that G has a tree-decomposition and a layering such that each bag has at most k vertices in each layer. The row treewidth of G is the minimum integer k such that G is isomorphic to a subgraph of H - P for some graph H of treewidth at most k and for some path P. It follows from the definitions that the layered treewidth of a graph is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded layered treewidth if and only if it has bounded row treewidth. However, it has been open whether row treewidth is bounded by a function of layered treewidth. This paper answers this question in the negative. In particular, for every integer k we describe a graph with layered treewidth 1 and row treewidth k. We also prove an analogous result for layered pathwidth and row pathwidth. [ABSTRACT FROM AUTHOR]

Given a graph G and an integer k, it is an NP-complete problem to decide whether G has a dominating set of size at most k. In this paper we study this problem for the Knödel Graph on n vertices using elementary number theory techniques. In particular, we show an explicit upper bound for the domination number of the Knödel Graph on n vertices any time that we can find a prime number p dividing n for which 2 is a primitive root. [ABSTRACT FROM AUTHOR]

The determining number of a graph G = (V,E) is the minimum cardinality of a set S ⊑ V such that pointwise stabilizer of S under the action of Aut(G) is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs. [ABSTRACT FROM AUTHOR]

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i. e. admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are far from being Hamiltonian, where a graph G on n vertices is far from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, locally Hamiltonian means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in (n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties that are testable in the bounded-degree model. [ABSTRACT FROM AUTHOR]

Let k and n be integers such that 1 ≤ k ≤ n 1, and let G be a simple graph of order n. The k-token graph Fk(G) of G is the graph whose vertices are the k-subsets of V (G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is an edge of G. In this paper we show that if G is a tree, then the connectivity of Fk(G) is equal to the minimum degree of Fk(G). [ABSTRACT FROM AUTHOR]

An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph whose arc set can be partitioned into k branchings, there always exists an equitable partition into k branchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and into b-branchings in digraphs. For matching forests, Király and Yokoi (2022) considered a tricriteria equitability based on the sizes of the matching forest, and the matching and branching therein. In contrast to this, we introduce a single-criterion equitability based on the number of covered vertices, which is plausible in the light of the delta-matroid structure of matching forests. While the existence of this equitable partition can be derived from a lemma in Király and Yokoi, we present its direct and simpler proof. For b-branchings, we define an equitability notion based on the size of the b-branching and the indegrees of all vertices, and prove that an equitable partition always exists. We then derive the integer decomposition property of the associated polytopes. [ABSTRACT FROM AUTHOR]

An outer-1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge. This paper establishes the local structure of outer-1- planar graphs by proving that each outer-1-planar graph contains one of the seventeen fixed configurations, and the list of those configurations is minimal in the sense that for each fixed configuration there exist outer-1-planar graphs containing this configuration that do not contain any of another sixteen configurations. There are two interesting applications of this structural theorem. First of all, we conclude that every (resp. maximal) outer-1-planar graph of minimum degree at least 2 has an edge with the sum of the degrees of its two end-vertices being at most 9 (resp. 7), and this upper bound is sharp. On the other hand, we show that the list 3-dynamic chromatic number of every outer-1-planar graph is at most 6, and this upper bound is best possible. [ABSTRACT FROM AUTHOR]

Let H = (V, F) be a simple hypergraph without loops. H is called linear if |f ∩g| ≤ 1 for any f, g ∈ F with f 6= g. The 2-section of H, denoted by [H]2, is a graph with V ([H]2) = V and for any u, v ∈ V ([H]2), uv ∈ E([H]2) if and only if there is f ∈ F such that u, v ∈ f. The treewidth of a graph is an important invariant in structural and algorithmic graph theory. In this paper, we consider the treewidth of the 2-section of a linear hypergraph. We will use the minimum degree, maximum degree, anti-rank and average rank of a linear hypergraph to determine the upper and lower bounds of the treewidth of its 2-section. Since for any graph G, there is a linear hypergraph H such that [H]2 ∼= G, we provide a method to estimate the bound of treewidth of graph by the parameters of the hypergraph. [ABSTRACT FROM AUTHOR]

In this paper, we prove a collection of results on graphical indices. We determine the extremal graphs attaining the maximal generalized Wiener index (e.g. the hyper-Wiener index) among all graphs with given matching number or independence number. This generalizes some work of Dankelmann, as well as some work of Chung. We also show alternative proofs for two recent results on maximizing the Wiener index and external Wiener index by deriving it from earlier results. We end with proving two conjectures. We prove that the maximum for the difference of the Wiener index and the eccentricity is attained by the path if the order n is at least 9 and that the maximum weighted Szeged index of graphs of given order is attained by the balanced complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values b ∈ {0, 1}, we obtain a formula for b-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of s-symmetric NCFs. We obtain the general formula of the cardinality of the set of n-variable s-symmetric Boolean NCFs for s = 1, . . ., n. In particular, we enumerate the strongly asymmetric Boolean NCFs. [ABSTRACT FROM AUTHOR]

Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d(u)+d(v) ≥ 3a whenever uv ∈ A(D) and vu ∈ A(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if d(u) + d(v) ≥ 3a − 1 whenever uv ∈ A(D) and vu ∈ A(D), then D is traceable. The lower bound 3a − 1 is tight. [ABSTRACT FROM AUTHOR]

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of split graphs, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either 2 or 3, under the Strong ExponentialTime Hypothesis (SETH) we cannot compute the diameter of an n-vertex m-edge split graph in less than quadratic time – in the size n + m of the input. Therefore it is worth to study the complexity of diameter computation on subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded clique-interval number and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the VC-dimension and the stabbing number of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: • For the k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in quasi linear time if k = o(log n) and in addition a corresponding ordering of the vertices in the clique is given. However, under SETH this cannot be done in truly subquadratic time for any k = ω(log n). • For the complements of k-clique-interval split graphs, we can compute their diameter in truly subquadratic time if k = O(1), and even in time O(km) if a corresponding ordering of the vertices in the stable set is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a k-clique interval ordering can always be computed in quasi linear time. We prove that it is the case for k = 1 and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs – including the ones mentioned above – have a bounded clique-interval number. [ABSTRACT FROM AUTHOR]

The Hausdorff distance is a relatively new measure of similarity of graphs. The notion of the Hausdorff distance considers a special kind of a common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. There was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this paper we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses the procedure that is based on the well known graph algorithm of finding the maximum bipartite matching. [ABSTRACT FROM AUTHOR]

A graph G is weighted–k–list–antimagic if for any vertex weighting ω: V (G) → R and any list assignment L: E(G) → 2R with |L(e)| ≥ |E(G)| + k there exists an edge labeling f such that f(e) ∈ L(e) for all e ∈ E(G), labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on n vertices having no K1 or K2 component is weighted–[ 4n/3 ] –list–antimagic. [ABSTRACT FROM AUTHOR]

The forbidden number forb(m,F), which denotes the maximum number of unique columns in an m-rowed (0, 1)- matrix with no submatrix that is a row and column permutation of F, has been widely studied in extremal set theory. Recently, this function was extended to r-matrices, whose entries lie in {0, 1, . . ., r - 1}. The combinatorics of the generalized forbidden number is less well-studied. In this paper, we provide exact bounds for many (0, 1)-matrices F, including all 2-rowed matrices when r > 3. We also prove a stability result for the 2 × 2 identity matrix. Along the way, we expose some interesting qualitative differences between the cases r = 2, r = 3, and r > 3. [ABSTRACT FROM AUTHOR]

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n4) time delay. In this paper, we improve their algorithm and achieve O(n3 log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15. [ABSTRACT FROM AUTHOR]

Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a k-anti-power, which is defined as a word of the form w(1)w(2) · · ·w(k), where w(1),w(2), . . .,w(k) are distinct words of the same length. For an infinite word w and a positive integer k, define APj(w, k) to be the set of all integers m such that wj+1wj+2 · · ·wj+km is a k-anti-power, where wi denotes the i-th letter of w. Define also Fj (k) = (2Z+ - 1) \ APj(t, k), where t denotes the Thue-Morse word. For all k 2 Z+, j(k) = min(APj(t, k)) is a well-defined positive integer, and for k 2 Z+ sufficiently large, Γj (k) = sup((2Z+ -1)\Fj (k)) is a well-defined odd positive integer. In his 2018 paper, Defant shows that 0(k) and Γ0(k) grow linearly in k. We generalize Defant's methods to prove that j(k) and ϒj(k) grow linearly in k for any nonnegative integer j. In particular, we show that 1/10 ≤ liminf k!1 (j(k)/k) ≤ 9/10 and 1/5 ≤ limsup k!1 (j(k)/k) ≤ 3/2. Additionally, we show that liminf k!1 (ϒj(k)/k) = 3/2 and limsup k!1 (Γj (k)/k) = 3. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥K + 1 and U ≥2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete. [ABSTRACT FROM AUTHOR]

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m+n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn6+O(m+n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn7+O(m+n). While this does not improve upon a recently announced bound of ⌈m3⌉⌈n3⌉+O(mn--√) [Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179. [ABSTRACT FROM AUTHOR]

It is commonly believed that real networks are scale-free and the fraction of nodes P(k) with degree k satisfies the power-law P(k) / k-γ for k > kmin > 0. Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the kmin varies very slowly to the extent of being uniform as compared to the degree distribution for k > kmin. In this paper, we propose a model that describes this particular degree distribution for the whole range of k > 0. We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it to an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform a comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by this model with that of real-world networks. [ABSTRACT FROM AUTHOR]