Search

Abstract: For positive integers , an -labeling of a digraph D is a function f from into the set of nonnegative integers such that if x is adjacent to y in D and if x is of distance two to y in D. Elements of the image of f are called labels. The -labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an -labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. [Copyright &y& Elsevier]

Abstract: This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and and , respectively. We also discuss permutations in avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers. [Copyright &y& Elsevier]

Given a set A ⊆ S n of m permutations of { 1 , 2 , ... , n } and a distance function d , the median problem consists of finding a permutation π ∗ that is the "closest" of the m given permutations. Here, we study the problem under the Kendall- τ distance which counts the number of order disagreements between pairs of elements of two permutations. This problem has been proved to be NP-hard when m ≥ 4 , m even. In this article, which is a full version of the conference paper Milosz and Hamel (2016), we investigate new theoretical properties of A that solve the relative order between pairs of elements in median permutations of A , thus drastically reducing the search space of the problem. The resulting preprocessing of the problem is implemented with a Branch-and-Bound solving algorithm. We analyze its performance on randomly generated data and on real data. [ABSTRACT FROM AUTHOR]

In this paper, we study Horn formulas from the perspective of read-once resolution refutations (RORs). A Horn formula is a Boolean formula in conjunctive normal form (CNF), in which each clause contains at most one positive literal. Horn formulas are used in a number of domains, including program verification, logic programming, and econometrics. In particular, deduction in ProLog is based on unification. Unification is based on resolution and instantiation. Resolution is a system used to prove the infeasibility of Boolean formulas. It is important to note that resolution is both sound and complete. However, resolution is inefficient in the following sense: There exist CNF formulas with resolution refutations whose lengths are bounded below by an exponential function of the input size. At the same time, these formulas admit shorter (polynomially bounded) proofs of infeasibility in other proof systems, such as Frege Systems. Despite this inefficiency, resolution is simple and easy to implement and hence used in a wide variety of theorem provers. In this paper, we study two variants of resolution. These are read-once resolution (ROR) and read-once unit resolution (UROR). Both ROR and UROR are sound. However, they are incomplete since there exist infeasible Boolean formulas which do not have either an ROR or a UROR. In this paper, we look at the problems of determining if a Horn formula has an ROR or a UROR. We also examine the problem of finding the optimal length ROR of a Horn formula from both the computational complexity and the approximation perspectives. Finally, we analyze the copy complexity of Horn formulas with respect to URORs. [ABSTRACT FROM AUTHOR]

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1- product of matrices S 1 ∈ R m 1 × n 1 , S 2 ∈ R m 2 × n 2 is a matrix in R (m 1 + m 2) × (n 1 n 2) whose columns are the concatenation of each column of S 1 with each column of S 2. The k - product generalizes the 1-product, by taking as input two matrices S 1 , S 2 together with k − 1 special rows of each of those matrices, and outputting a certain composition of S 1 , S 2 . Our first result is a polynomial time algorithm for the following problem: given a matrix S , is S a k -product of some matrices, up to permutation of rows and columns? Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information from information theory. Our study is motivated by a close link between the 1-product of matrices and the Cartesian product of polytopes, and more generally between the k -product of matrices and the glued product of polytopes. These connections rely on the concept of a slack matrix, which gives an algebraic representation of classes of affinely equivalent polytopes. The slack matrix recognition problem is the problem of determining whether a given matrix is a slack matrix. This is an intriguing problem whose complexity is unknown. Our algorithm reduces the problem to instances which cannot be expressed as k -products of smaller matrices. In the second part of the paper, we give a combinatorial interpretation of k -products for two well-known classes of polytopes: 2-level matroid base polytopes and stable set polytopes of perfect graphs. We also show that the slack matrix recognition problem is polynomial-time solvable for such polytopes. Those two classes are special cases of 2-level polytopes, for which we conjecture that the slack matrix recognition problem is polynomial-time solvable. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the performance of message-passing algorithms for the weighted min–max flow (WMMF) problem which was introduced by Ichimori et al. (1980). WMMF was well studied in combinational optimization, as it provides important applications in time transportation problem and the storage management problem. We develop a message-passing algorithm called min–max belief propagation (BP) for determining the optimal solution of WMMF. As the main result of this paper, we prove that for a digraph of size n , BP converges to the optimal solution within O (n 3) time after O (n) iterations if the optimal solution of the underlying min–max flow problem instance is unique. To the best of our knowledge, the fastest polynomial time algorithm for WMMF runs in essentially O (n 6) time among the known algorithms, where n is the number of vertices. On the other hand, it is one of a very few instances where BP is proved correct with fully-polynomial running time. [ABSTRACT FROM AUTHOR]

Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph G are contaminated initially, before the process starts. By the q -forcing rule, a contaminated vertex having at most q uncontaminated neighbors enforces all the neighbors to become contaminated, while by the p -percolation rule, an uncontaminated vertex becomes contaminated if at least p of its neighbors are contaminated. If given a set S of initially contaminated vertices all vertices eventually become contaminated when continuously applying the q -forcing rule (respectively the p -percolation rule), S is called a q -forcing set (respectively, a p -percolating set) in G. In this paper, we consider sets S that are at the same time q -forcing sets and p -percolating sets, and call them (p , q) -spreading sets. Given positive integers p and q , the minimum cardinality of a (p , q) -spreading set in G is a (p , q) -spreading number, σ (p , q) (G) , of G. While q -forcing sets have been studied in a dozen of papers, the decision version of the corresponding graph invariant has not been considered earlier, and we fill the gap by proving its NP-completeness. This, in turn, enables us to prove the NP-completeness of the decision version of the (p , q) -spreading number in graphs for an arbitrary choice of p and q. Again, for every p ∈ N and q ∈ N ∪ { ∞ } , we find a linear-time algorithm for determining the (p , q) -spreading number of a tree, where in the case p ≥ 2 we apply Riedl's algorithm from [Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64] on p -percolation in trees. In addition, we present a lower and an upper bound on the (p , q) -spreading number of a tree and characterize extremal families of trees. In the case of square grids, we combine some results of Bollobás from [The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006], and the AIM Minimum Rank-Special Graphs Work Group from [Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 2008 1628–1648], and new results on (2 , 1) -spreading and (4 , q) -spreading to obtain σ (p , q) (P m □ P n) for all (p , q) ∈ (N ∖ { 3 }) × (N ∪ { ∞ }) and all m , n ∈ N. [ABSTRACT FROM AUTHOR]

The concept of conflict-free connection coloring of graphs was introduced by Czap et al. in 2018. It has been the subject of several papers, which is closely related with conflict-free coloring of hypergraphs. In this survey we bring together most of the results and papers on this topic. We begin with an introduction, and then try to organize the work into three categories, conflict-free connection number, strong conflict-free connection number and conflict-free vertex-connection number. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

A graph G = ({ 1 , 2 , ... , n } , E) is 12- representable if there is a word w over { 1 , 2 , ... , n } such that two vertices i and j with i < j are adjacent if and only if every j occurs before every i in w. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of 12-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs defined by pattern-avoiding words. Following this research direction, this paper studies 12-representable graphs defined by words that avoid a pattern p. Such graphs are trivial when p is of length 2. When p = 111, 121, 231, and 321, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where p = 123, 132, and 211, this paper provides forbidden pattern characterizations. • Classes of graphs 12-representable by pattern-avoiding words are introduced. • Among such classes, those with patterns of length at most 3 are investigated. • Some classes are equivalent to well-known classes such as trivially perfect graphs. • Forbidden pattern characterizations are provided for other classes. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to study the Laplacian eigenvalues of the extension of the zero divisor graph, Γ e (Z n) , for some particular values of n. We characterize the values of n that give the equality of the spectral radius and the second-smallest eigenvalue of Γ e (Z n). Finding Wiener index of Γ e (Z n) in terms of its Laplacian eigenvalues is another objective of this paper. [ABSTRACT FROM AUTHOR]

Constant dimension codes (CDCs) have drawn extensive attention due to their applications in random network coding. Bounds for the maximum possible size A q (n , d , k) of CDCs are the topic of many recent research papers. A construction of CDCs which combines the parallel linkage construction and two parallel versions of the subcode construction was presented by He et al. in 2022. In this paper, we improve the parallel subcode construction by changing the parameters of matrix blocks in the subcode construction. A new construction of CDCs is presented by combining the parallel linkage construction and our improved parallel subcode construction. Our construction generalizes the result of He et al.. It gives rise to some new lower bounds for CDCs, including A q (16 , 4 , 4) , A q (16 , 6 , 8) , A q (18 , 6 , 6) and A q (19 , 6 , 6). [ABSTRACT FROM AUTHOR]

In Evans and Francis (2022) and Hendel (2021) the authors investigated resistance distance in triangular grid graphs and observed several types of asymptotic behavior. This paper extends their work by studying the initial, non-asymptotic, behavior found when equivalent circuit transformations are performed, reducing the rows in the triangular grid graph one row at a time. The main conjecture characterizes, after reducing an arbitrary number of times an initial triangular grid all of whose edge resistances are identically one, when edge resistance values are less than, equal to, or greater than one. A special case of the conjecture is proven. The main theorem identifies patterns of repeating edge resistances arising in diagonals of a triangular grid reduced s times provided the original grid has at least 4 s rows of triangles. This paper also improves upon the notation, concepts, and proof techniques introduced by the authors previously. [ABSTRACT FROM AUTHOR]

"Which graphs are determined by their spectra (DS for short)?" is an important and challenging topic in spectral graph theory. Let G be an n -vertex graph with adjacency matrix A (G) and adjacency walk matrix W A (G) = [ e , A (G) e , ... , A n − 1 (G) e ]. We call G controllable if the rank of W A (G) is n over R and noncontrollable otherwise. In Wang (2017), the author gave a simple condition for a controllable graph to be determined by their generalized adjacency spectrum (DGAS for short). However, the result fails for noncontrollable graphs. In this paper, we consider the problem in the context of the generalized distance spectrum. Let G be a connected graph with distance matrix D. A graph G is determined by its generalized distance spectrum (DG D S for short) if any graph H sharing the same generalized distance spectrum with G must be isomorphic to G. The paper aims to extend the result in Wang (2017) from generalized adjacency spectrum to generalized distance spectrum. Besides, a simple arithmetic criterion is given to determine whether a connected graph is DG D S or not, which is applicable to some kind of noncontrollable graphs, e.g., regular graphs. [ABSTRACT FROM AUTHOR]

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [ABSTRACT FROM AUTHOR]

This paper studies three edge-removing games on graphs. In each game, there are two players and a simple graph G at the beginning. The players take turns removing at least one edge of a certain type from the current graph. The one who cannot move loses the game, and the other one, who plays the last move, wins. This paper gives results for these games on some interesting classes of graphs by either computing their Grundy numbers or proposing winning strategies. [ABSTRACT FROM AUTHOR]

The Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in King and Krohn (2010) and to admit a PTAS (Krohn et al., 2014; Friedrichs et al., 2016). The biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the ONE-SIDED TERRAIN GUARDING problem and the Clique Cover problem in chordal graphs. These theorems were proved in Katz and Roisman (2008) for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for DISCRETE ORTHOGONAL TERRAIN GUARDING in Ashok et al. (2018). We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for Discrete Terrain Guarding. [ABSTRACT FROM AUTHOR]

In the original article (Gutman et al., 2014), the authors state that the Wiener index (total distance) of an Eulerian graph is maximized by the cycle. We explain that the initial proof contains a flaw and note that it is a corollary of a result by Plesník, since an Eulerian graph is 2-edge-connected. The same incorrect proof is used in two referencing papers, (Liu et al., 2019) and (Cai et al., 2021). We give proofs of the main results of those papers and the 2-edge-connected analogues. [ABSTRACT FROM AUTHOR]

Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to study word-representability of graphs using a technique of homomorphisms. As a proof of concept, we apply our method to show word-representability of the simplified graph of overlapping permutations that we introduce in this paper. For another application, we obtain results on word-representability of certain subgraphs of simplified de Bruijn graphs that were introduced recently by Petyuk and studied in the context of word-representability. [ABSTRACT FROM AUTHOR]

Paintability of graphs, which is also called online choosability of graphs, was introduced by Schauz and by Zhu in 2009, and has been studied in point of the difference from choosability of graphs. Compared with the choice number and the chromatic number, it is much more difficult to determine the paint number of a given graph. For example, even the 3-paintable complete bipartite graphs have not been characterized yet. In this paper, we focus on the paintability of complete bipartite graphs, especially m -paintability of K m + 1 , r. Let r OL (m) denote the least integer r such that K m + 1 , r is not m -paintable. In this paper, we determine the order of r OL (m) as r OL (m) = Θ (m m − 1). Let r (m) denote the least r such that K m + 1 , r is not m -choosable, for which Hoffman and Johnson Jr. determined as r (m) = m m − (m − 1) m = Θ (m m). As a corollary, we can show that r OL (m) / r (m) tends to 0 when m goes to infinity. [ABSTRACT FROM AUTHOR]

The chromatic index , χ ′ (G) , is the smallest integer k for which a graph G has a proper edge coloring. The Classification Problem involves determining whether a graph G is Class 1 ( χ ′ (G) = Δ (G)) or Class 2 ( χ ′ (G) = Δ (G) + 1). It is known that subgraph-overfull graphs must be Class 2. In this paper we are concerned with the Classification Problem for split graphs G [ Q ∪ S ] where Q is a clique and S is an independent set. When Δ (G) is odd, G is known to be Class 1. The original proof presented by Chen et al. (1995) has a minor flaw which we detail in this paper while also clarifying that it does not compromise their result. We prove that their technique can be adapted in a non-trivial way to show that some split graphs with even Δ (G) are also Class 1. We show that to solve the Classification Problem for split graphs it suffices to consider that all vertices in Q have degree Δ (G). Considering the subset X of S of the vertices of degree at most Δ (G) / 2 , we show that if the neighborhood of X has at least ⌊ | Q | / 2 ⌋ vertices, then G is Class 1; in the remaining cases we characterize the subgraph-overfull split graphs. • Correction of a flaw in the proof that odd maximum degree split graphs are Class 1. • Proof that certain split graphs with even maximum degree are Class 1. • Characterization of the split graphs which are subgraph-overfull, and thus Class 2. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in algorithms that take in input an arbitrary graph G , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of G which fulfil a given property Π. All over this paper, we study several different properties Π , and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, maximal induced cographs and maximal threshold graphs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal stable sets of an auxiliary graph. For cographs and threshold graphs, the algorithms rely on a framework recently introduced by Conte & Uno (2019) called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property Π that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every non-trivial hereditary property Π. We extend the hardness result to some specific edge version of the extension problem. [ABSTRACT FROM AUTHOR]

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

A graph G is called (k 1 , k 2) -Hamilton-connected, if for any two vertex disjoint subsets X = { x 1 , x 2 , ... , x k 1 } and U = { u 1 , u 2 , ... , u k 2 } , G contains a spanning family F of k 1 k 2 internally vertex disjoint paths such that for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , F contains an x i u j path. Let σ 2 (G) be the minimum value of deg (u) + deg (v) over all pairs { u , v } of non-adjacent vertices in G. In this paper, we prove that an n -vertex graph G is (2 , k) -Hamilton-connected if G is (5 k − 4) -connected with σ 2 (G) ≥ n + k − 2 where k ≥ 2. We also prove that if σ 2 (G) ≥ n + k 1 k 2 − 2 with k 1 , k 2 ≥ 2 , then G is (k 1 , k 2) -Hamilton-connected. Moreover, these requirements of σ 2 are tight. • This paper is motivated by k -fan connected graphs, we define (k 1 , k 2) -Hamilton-connected graphs. • This paper gives a sufficient condition for a graph to be (2 , k) -Hamilton-connected. • The results provide tight, sufficient, σ 2 (G) -conditions. • We extend the properties of Hamilton-connectedness and being k -linked. [ABSTRACT FROM AUTHOR]

The biclique B of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph K B (G) of a graph G is the graph with the bicliques of G as its vertices where two vertices of K B (G) are adjacent if and only if they have a common vertex in G. In this paper, we disprove a conjecture of Groshaus and Montero concerning Helly property of biclique graphs (Groshaus and Montero, 2021) and two conjectures of Montero concerning vertex removal in biclique graphs (Montero, 2022). In addition, we confirm a conjecture of Montero about the structural characterization of biclique graphs in the same paper. [ABSTRACT FROM AUTHOR]

Let (0 , a 1 , ... , a d − 1) n denote the function f n (x 0 , x 1 , ... , x n − 1) of degree d in n variables generated by the monomial x 0 x a 1 ⋯ x a d − 1 and having the property that f n is invariant under cyclic permutations of the variables. Such a function f n is called monomial rotation symmetric (MRS). Much of this paper extends the work on quadratic MRS functions in a 2020 paper of the authors to the case of binomial RS functions, that is sums of two quadratic MRS functions. There are also some results for the sum of any number of quadratic MRS functions. [ABSTRACT FROM AUTHOR]

El Sahili conjectured that every oriented n -path, where n ≥ 8 , is contained in every n -chromatic digraph. This conjecture was confirmed by Gallai–Hasse–Roy–Vitaver's theorem for directed paths and by Addario-Berry et al. for oriented paths with two blocks. A block of an oriented path is a maximal directed subpath. El Joubbeh showed that every (4 n − 4) -chromatic digraph contains every oriented n -path with three blocks. For oriented paths with more than three blocks, Addario-Berry et al. established that every oriented n -tree, and hence every oriented n -path with any number of blocks, is contained in every ( n 2 2 − n 2 + 1) -chromatic digraph. This paper proposes an improvement to the bound on the chromatic number for digraphs that must include all paths consisting of four blocks. In fact, we extend El Joubbeh's bound on the chromatic number from (4 n − 4) for digraphs that should contain every n -path with three blocks to (4 n − 2) for digraphs that should be contain every n -path with four blocks. This bound surpasses the one provided by Addario-Berry et al. Furthermore, we show that every oriented n -path with t blocks, t ≥ 4 , is contained in every (4 r (t) n + q (t)) -chromatic digraph where r (t) = log 2 (t − 1) and q (t) = − 20 7 8 r (t) − 1 + 6 7 . Finally, the paper highlights an improvement in the bound of Addario-Berry et al. for n -paths with t blocks, where t ≤ n − 1 2 + 1. [ABSTRACT FROM AUTHOR]