Search

A graph is (I , F) - partitionable if its vertex set can be partitioned into two parts such that one part I is an independent set, and the other F induces a forest. A graph is k - degenerate if every subgraph H contains a vertex of degree at most k in H. Bernshteyn and Lee defined a generalization of k -degenerate graphs, which is called weakly k -degenerate. In this paper, we show that planar graphs without 4-, 7-, 9-cycles, and 5-cycles normally adjacent to 3-cycles are both (I , F) -partitionable and weakly 2-degenerate. [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]

A matching in a graph G is a collection of edges of G such that no two of them share a vertex. The number of all matchings in G is called its Hosoya index. In this paper, we compute Hosoya indices of several classes of unbranched polymers made of cycles of the same lengths arranged around a middle path and decorated by attaching to each vertex, a given number of pendent vertices or thorns. We establish linear recurrences satisfied by those numbers and obtain explicit formulas in terms of Fibonacci polynomials and their generalizations. Some possible directions of future research are also indicated. [ABSTRACT FROM AUTHOR]

Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason's extension of Smith's Theorem. Our proof was not algorithmic. In this paper, I extend Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason's Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E (T) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about "good" trees in general graphs. My proof provides an algorithm for finding a second "good" tree. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with vertex set V , where the distance between two vertices is the length of a shortest path between them. A set S ⊆ V is [ 1 , 2 ] -resolving if each vertex of G is at most distance-two away from a vertex in S and, given a pair of distinct vertices not in S , either there is a vertex in S adjacent to exactly one member of the given pair, or there are two vertices in S each of which is distance-two from exactly one member of the given pair. The [ 1 , 2 ] -dimension of G is the minimum cardinality of a [ 1 , 2 ] -resolving set of G. In this paper, we study the [ 1 , 2 ] -dimension of graphs by proving that the [ 1 , 2 ] -dimension problem is an NP-complete problem, and determine the [ 1 , 2 ] -dimension of some classes of graphs, such as paths, cycles, and full k -ary trees. We also introduce a generalization of metric dimension of which the (original) metric dimension and the [ 1 , 2 ] -dimension, as well as other metric dimension variants in the literature, are special instances. [ABSTRACT FROM AUTHOR]

A graph is k -degenerate if every subgraph H has a vertex v with d H (v) ≤ k. The class of degenerate graphs plays an important role in the graph coloring theory. Observed that every k -degenerate graph is (k + 1) -choosable and (k + 1) -DP-colorable. Bernshteyn and Lee defined a generalization of k -degenerate graphs, which is called weakly k -degenerate. The weak degeneracy plus one is an upper bound for many graph coloring parameters, such as choice number, DP-chromatic number and DP-paint number. In this paper, we give two sufficient conditions for a plane graph without 4- and 6-cycles to be weakly 2-degenerate, which implies that every such graph is 3-DP-colorable and near-bipartite, where a graph is near-bipartite if its vertex set can be partitioned into an independent set and an acyclic set. [ABSTRACT FROM AUTHOR]

The generalized connectivity is a generalization of traditional connectivity, which is a parameter that can measure the capability of connecting vertices in G. The pancake graph has some desirable properties to design interconnection networks. In this paper, we obtain that the generalized 4-connectivity of pancake graph P n is n − 2 , that is, there are (n − 2) internally disjoint S -trees connecting any four arbitrary vertices x , y , z and w of P n , where S = { x , y , z , w }. As a corollary, the generalized 3-connectivity of the pancake graph P n can be obtained directly. [ABSTRACT FROM AUTHOR]

The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum b -matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the k -degenerate graphs, whose approximation ratios are α + 2 k − 2 and α k , where α is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an (α + k) -approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are k -systems with independence oracles. [ABSTRACT FROM AUTHOR]

This paper is inspired by the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph. [ABSTRACT FROM AUTHOR]

DP-coloring as a generalization of list coloring was introduced recently by Dvořák and Postle. The D P -chromatic number of G , denoted by χ D P (G) , is the minimum number k such that G is D P − k -colorable. The variation of the Randić index R ′ (G) of a graph G is defined as the sum of the weights 1 m a x { d (u) , d (v) } of all edges u v of G , where d (u) is the degree of the vertex u in G. In this paper, we show that for any graph G of order n , χ D P (G) ≤ 2 R ′ (G) , and this bound is sharp for all n and 2 ≤ χ D P (G) ≤ n. [ABSTRACT FROM AUTHOR]

In this paper, we give a characterization or a property for trees T such that a component of T − e is a specific path for each edge e of T , and as corollaries of them, we obtain upper bounds on some domination-type invariants. We demonstrate how our results can be used by taking a recent result, and give a sharp upper bound on the c -self domination number which was recently defined as a generalization of some well-studied invariants. [ABSTRACT FROM AUTHOR]

As a generalization of p -center location problems, p - k - max problems minimize the k th largest weighted distance to the customers. In this way, outlier facilities can be detected automatically and excluded from consideration when locating new facilities. Similar to p -center problems, p - k - max problems often have many alternative optimal solutions. Knowledge of the complete optimal set allows to select a most preferred solution using secondary criteria. In this paper, a general solution method is suggested that guarantees to find all alternative optimal solutions of p - k - max problems on networks. This is realized by performing a local analysis on the edges of the underlying graph and identifying edge segments on which the p - k - max function is linear. It is shown that the complete optimal set can be represented by an extended finite dominating set (FDS) which is of polynomial size for fixed values of p. Numerical tests indicate that computing the set of optimal solutions compared to the computation of a single optimal solution of a p - k - max problem requires on average less than 15% additional computing effort. This computational efficiency allows one to select the most preferred solution among them using secondary objectives, like backup coverage or the Weber function. [ABSTRACT FROM AUTHOR]

A digraph D = (V (D) , A (D)) of order n ≥ 3 is pancyclic , whenever D contains a directed cycle of length k for each k ∈ { 3 , ... , n } ; and D is vertex-pancyclic iff, for each vertex v ∈ V (D) and each k ∈ { 3 , ... , n } , D contains a directed cycle of length k passing through v. Let D 1 , D 2 , ..., D k be a collection of pairwise vertex disjoint digraphs. The generalized sum (g.s.) of D 1 , D 2 , ..., D k , denoted by ⊕ i = 1 k D i or D 1 ⊕ D 2 ⊕ ⋯ ⊕ D k , is the set of all digraphs D satisfying: (i) V (D) = ⋃ i = 1 k V (D i) , (ii) D 〈 V (D i) 〉 ≅ D i for i = 1 , 2 , ... , k , and (iii) for each pair of vertices belonging to different summands of D , there is exactly one arc between them, with an arbitrary but fixed direction. A digraph D in ⊕ i = 1 k D i will be called a generalized sum (g.s.) of D 1 , D 2 , ..., D k. Let D 1 , D 2 , ..., D k be a collection of k pairwise vertex disjoint Hamiltonian digraphs, in this paper we give simple sufficient conditions for a digraph D ∈ ⊕ i = 1 k D i to be vertex-pancyclic. This result extends a result obtained by Cordero-Michel et al. (2016). [ABSTRACT FROM AUTHOR]

In this paper we present bounds on the radius and diameter of graphs of girth at least 6 and for (C 4 , C 5) -free graphs, i.e., graphs not containing cycles of length 4 or 5. We show that the diameter of a graph G of girth at least 6 is at most 3 n δ 2 − δ + 1 − 1 , and the radius is at most 3 n 2 (δ 2 − δ + 1) + 10 , where n is the order and δ the minimum degree of G. If δ − 1 is a prime power, then both bounds are sharp apart from an additive constant. For graphs of large maximum degree Δ , we show that these bounds can be improved to 3 n − Δ δ δ 2 − δ + 1 − 3 (δ − 1) Δ (δ − 2) δ 2 − δ + 1 + 10 for the diameter, and 3 n − 3 Δ δ 2 (δ 2 − δ + 1) − 3 (δ − 1) Δ (δ − 2) 2 (δ 2 − δ + 1) + 22 for the radius. We further show that only slightly weaker bounds hold for (C 4 , C 5) -free graphs. As a by-product we obtain a result on a generalisation of cages. For given δ , Δ ∈ N with Δ ≥ δ let n (δ , Δ , g) be the minimum order of a graph of girth g , minimum degree δ and maximum degree Δ. Then n (δ , Δ , 6) ≥ Δ δ + (δ − 1) Δ (δ − 2) + 3 2 . If δ − 1 is a prime power, then there exist infinitely many values of Δ such that, for δ constant and Δ large, n (δ , Δ , 6) = δ Δ + O (Δ). [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the 2-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in O ( n m ) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O ( n m 2 ) time. In this paper, we investigate the relationship between 2-vertex-connected components and dominator trees. We also consider three applications of our new algorithm, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph. [ABSTRACT FROM AUTHOR]

A spider is a tree with at most one branch (a vertex of degree at least 3) centred at the branch if it exists, and centred at any vertex otherwise. A graph G is arachnoid if for any vertex v of G , there exists a spanning spider of G centred at v —in other words: there are spiders everywhere! Hypotraceable graphs are non-traceable graphs in which all vertex-deleted subgraphs are traceable. Gargano et al. (2004) defined arachnoid graphs as natural generalisations of traceable graphs and asked for the existence of arachnoid graphs that are (i) non-traceable and non-hypotraceable, or (ii) in which some vertex is the centre of only spiders with more than three legs. An affirmative answer to (ii) implies an affirmative answer to (i). While non-traceable, non-hypotraceable arachnoid graphs were described in Wiener (2017), (ii) remained open. In this paper we give an affirmative answer to this question and discuss spanning spiders whose legs must have some minimum length. [ABSTRACT FROM AUTHOR]

The (t , r) broadcast domination is a generalization of domination in a graph. In this paper we prove a conjecture by Drews, Harris, and Randolph about the minimal density of towers in Z 2 that provide a (t , 3) domination broadcast for t ≥ 17 and explore generalizations. Additionally, we determine the (t , r) broadcast domination number of powers of paths, P n (k) and powers of cycles, C n (k) . [ABSTRACT FROM AUTHOR]

Techniques of producing new combinatorial structures from old ones are commonly called trades. The switching principle applies for a broad class of designs: it is a local transformation that modifies two columns of the incidence matrix. In this paper, we present a construction, which is a generalization of the switching transform for the class of Steiner 2-designs. We call this construction paramodification of Steiner 2-designs, since it modifies the parallelism of a subsystem. We study in more detail the paramodifications of affine planes, Steiner triple systems, and abstract unitals. Computational results show that paramodification can construct many new unitals. [ABSTRACT FROM AUTHOR]

In this paper, we study the single machine scheduling to minimize the total earliness and tardiness (i.e., the total deviation) with generalized or assignable due dates. Under the assumption of assignable due dates, the due dates are treated as variables and must be assigned to the individual jobs in a schedule. The assumption of generalized due dates is a special version of assignable due dates, in which the due dates are sequenced in the EDD order and assigned to the jobs by the increasing order of their completion times so that the i th completed job receives the i th due date. The exact complexity of the two problems has been reported open in the literature. We show in this paper that the two problems are unary NP-hard. [ABSTRACT FROM AUTHOR]

The well-known Randić index of a graph G is defined as R(G) = ∑(du⋅dv)−1/2, where the sum is taken over all edges uv ∈ E(G) and du and dv denote the degrees of u and v, respectively. Recently, it was found useful to use its simplified modification: R′(G) = ∑(max{du, dv})−1, which represents a lower bound for the Randić index. In this paper we introduce generalizations of R′ and its counterpart, R″, defined as R'α (G) = ∑min{duα, dvα} and R"α(G) = ∑max{duα, dvα}, for any real number α. Clearly, the former is a lower bound for the generalized Randić index, and the latter is its upper bound. We study extremal values of R'α and R"α, and present extremal graphs within the classes of connected graphs and trees. We conclude the paper with several problems. [ABSTRACT FROM AUTHOR]

The h -good neighbor connectivity κ h (G) is an important parameter to evaluate the fault tolerance of an interconnection network G. So far, almost all known results of κ h (G) are about small h ′ s except the hypercubes, the star graphs, the k -ary n -cubes and hierarchical hypercube network H H C n et al. In this paper, we focus on κ h (B n , k) for the (n , k) -bubble-sort network B n , k , which is a generalization of the bubble-sort graph B n as it is a special case of (n , k) -bubble-sort networks for k = n − 1. We show that κ h (B n , k) = n + h (k − 2) − 1 for 2 ≤ k ≤ ⌈ n + 3 2 ⌉ and 0 ≤ h ≤ ⌊ n − 3 2 ⌋ , which implies that at least n + h (k − 2) − 1 vertices of B n , k have to be deleted to get a disconnected graph without vertices of degree less than h. [ABSTRACT FROM AUTHOR]

On-line list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, χ P (G) , (the minimum number of colors needed for an on-line coloring of G) and the DP-chromatic number, χ D P (G) , (the minimum number of colors needed for a DP-coloring of G) is at least the list chromatic number of G and can be much larger. On the other hand, each of them has a number of useful properties. The main goal of the paper is to introduce a common generalization, on-line DP-coloring, of on-line list coloring and DP-coloring and to study its properties. It turns out that many upper bounds on the DP-chromatic number are also upper bounds on the on-line DP-chromatic number. On the other hand, we show that this invariant of a graph can be larger than each of the DP-chromatic number and the paint number. As a biproduct we present examples of graphs G with χ P (G) > χ D P (G). [ABSTRACT FROM AUTHOR]

The notion of repetition of factors in words is central to combinatorics on words. A recent generalisation of this concept considers repetitions under permutations: given an alphabet Σ and a morphism or antimorphism f on Σ ∗ , whose restriction to Σ is a permutation, w is an f ] -repetition if there exists γ ∈ Σ ∗ , an integer k ≥ 2 , and the positive integers i 1 , ... , i k such that w = f i 1 (γ) f i 2 (γ) ⋯ f i k (γ). In this paper, we extend a series of classical repetition enforcing word equations to this general setting to obtain a series of word equations whose solutions are f ] -repetitions. [ABSTRACT FROM AUTHOR]

The concept of cycle energy (C E) was introduced in the chemical literature as early as in the 1970s. In this paper, three theorems are proven, showing the dependence of C E on the size of the corresponding cycle. Cycles of size 4 r + 2 and 2 r + 1 increase C E , whereas cycles of size 4 r decrease C E. Some generalizations of these results are also offered. [ABSTRACT FROM AUTHOR]

The connectivity is an important measurement for the fault-tolerance of networks. The structure connectivity and substructure connectivity are two generalizations of the classical connectivity. For a fixed graph H , a set F of subgraphs of G is called an H -structure cut (resp., H -substructure cut) of G , if G − ∪ F ∈ F V (F) is disconnected and every element of F is isomorphic to H (resp., a connected subgraph of H). The H -structure connectivity (resp., H -substructure connectivity) of G , denoted by κ (G ; H) (resp., κ s (G ; H)), is the cardinality of a minimal H -structure cut (resp., H -substructure cut) of G. In this paper, we will establish both κ (S n ; H) and κ s (S n , H) for every H ∈ { K 1 , K 1 , 1 , K 1 , 2 , ... , K 1 , n − 2 , P 4 , P 5 , C 6 } , where S n is the n -dimensional star graph. These results will show that star networks are highly tolerant of structure faults. [ABSTRACT FROM AUTHOR]

Recently the matcher game was introduced. In this game, two players create a maximal matching by one player repeatedly choosing a vertex and the other player choosing a K 2 containing that vertex. One player tries to minimize the result and the other to maximize the result. In this paper we propose a generalization of this game where K 2 is replaced by a general graph F. We focus here on the case of F = P 3 . We provide some general results and lower bounds for the game, investigate the graphs where the game ends with all vertices taken, and calculate the value for some specific families of graphs. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of b -branchings in digraphs, which is a generalization of branchings serving as a counterpart of b -matchings. Here b is a positive integer vector on the vertex set of a digraph D , and a b -branching is defined as a common independent set of two matroids defined by b : an arc set is a b -branching if it has, for every vertex v of D , at most b (v) arcs entering v , and it is an independent set of a certain sparsity matroid defined by b and D. We demonstrate that b -branchings yield an appropriate generalization of branchings by extending several classic results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b -branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b -branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b -branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b (v) arcs sharing the terminal vertex v. [ABSTRACT FROM AUTHOR]

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle (2017). Kim and Ozeki proved that planar graphs without k -cycles where k = 3 , 4 , 5 , or 6 are DP-4-colorable. In this paper, we prove that every planar graph G without k -cycles adjacent to triangles is DP-4-colorable for k = 5 , 6 , which implies that every planar graph G without k -cycles adjacent to triangles is 4-choosable for k = 5 , 6. This extends the result of Kim and Ozeki on 3-, 5-, and 6-cycles. [ABSTRACT FROM AUTHOR]

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu (2017) recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the FMP number and the FSMP number for arrangement graphs. In addition, all the optimal fractional strong matching preclusion sets of these graphs are categorized. [ABSTRACT FROM AUTHOR]

Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the spanning arborescence packing problem to a matroid-based arborescence packing problem and gave a necessary and sufficient condition for the existence of a packing and a polynomial-time algorithm. In this paper, a generalization of this latter problem – the polymatroid-based arborescence packing problem – is considered. Two problem settings are formulated: an unsplittable version and a splittable version. The unsplittable version is shown to be strongly NP-complete. Whereas, the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, can be solved in strongly polynomial time. For convenience, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for the splittable version. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we explore the connections between two classes of polyominoes, namely the permutominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization. On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudo-hexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as , where denotes the path traveled in the opposite direction. In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier–Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed , each word such that is pseudo-square is prefix of a unique infinite word with period . Also, we show that are centrosymmetric, i.e. they are fixed by rotation of angle . The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods. [Copyright &y& Elsevier]

Abstract: Let be a family of subsets of an -element set. Sperner’s theorem says that if there is no inclusion among the members of then the largest family under this condition is the one containing all -element subsets. The present paper surveys certain generalizations of this theorem. The maximum size of is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let be a poset. The maximum size of a family which does not contain as a (not-necessarily induced) subposet is denoted by . The paper is based on a lecture of the author at the Jubilee Conference on Discrete Mathematics [Banasthali University, January 11–13, 2009], but it was somewhat updated in December 2010. [Copyright &y& Elsevier]

The Haemers–Mathon bound states that t ≤ s 3 + t 2 (s 2 − s + 1) for any finite regular near hexagon with parameters (s , t , t 2) , s ≥ 2. In this paper, we generalize this bound to arbitrary finite near hexagons with an order. The obtained inequality involves the orders of the quads through a given line. [ABSTRACT FROM AUTHOR]

Chronological interval digraphs are a natural directed analogue of interval graphs. They admit elegant characterizations as well as efficient recognition algorithms. Recently, a generalization of chronological interval digraphs to 2-dimensional space called chronological rectangle digraphs was introduced and studied. Although many interesting properties of chronological rectangle digraphs have been discovered, the most fundamental question of whether this class of digraphs can be recognized in polynomial-time remains unanswered. This is largely due to the lack of a good structural characterization for the class. In this paper, we study chronological rectangle digraphs which are also two-terminal series–parallel. We show that this restricted class of digraphs admits a forbidden induced subdigraph characterization, which leads to a polynomial-time recognition algorithm for this class of digraphs. [ABSTRACT FROM AUTHOR]

Abstract: The competition graph of a digraph, introduced by Cohen in 1968, has been extensively studied. More recently, in 2000, Cho, Kim, and Nam defined the -step competition graph. In this paper, we offer another generalization of the competition graph. We define the -step competition graph of a digraph , denoted , as the graph on where if and only if there exists a vertex , such that either and or and . In this paper, we characterize the -step competition graphs of tournaments and extend our results to the -step competition graph of a tournament. [ABSTRACT FROM AUTHOR]

Abstract Let S ⊆ V (G) and κ G (S) denote the maximum number r of edge-disjoint trees T 1 , T 2 , ... , T r in G such that V (T i) ⋂ V (T j) = S for any i , j ∈ { 1 , 2 , ... , r } and i ≠ j. For an integer k with 2 ≤ k ≤ n , the generalized k - connectivity of a graph G is defined as κ k (G) = m i n { κ G (S) | S ⊆ V (G) and | S | = k }. The generalized k -connectivity is a generalization of traditional connectivity. In this paper, we focus on the alternating group graphsand (n , k) -star graphs, denoted by A G n and S n , k , respectively. We study the generalized3-connectivity of the two kinds of graphs and show that κ 3 (A G n) = 2 n − 5 for n ≥ 4 and κ 3 (S n , k) = n − 2 for n ≥ k + 1 and k ≥ 4 , which generalize the known result about star graphs given by Li et al. (2016). In addition, as the alternating group network A N n is isomorphic to S n , k for k = n − 2 , the generalized 3-connectivity of A N n for n ≥ 6 can be obtained directly. [ABSTRACT FROM AUTHOR]

M-convex functions, which are a generalization of valuated matroids, play a central role in discrete convex analysis. Quadratic M-convex functions constitute a basic and important subclass of M-convex functions, which has a close relationship with phylogenetics as well as valued constraint satisfaction problems. In this paper, we consider the quadraticM-convexity testing problem (QMCTP), which is the problem of deciding whether a given quadratic function on { 0 , 1 } n is M-convex. We show that QMCTP is co-NP-complete in general, but is polynomial-time solvable under a natural assumption. Furthermore, we propose an O ( n 2 ) -time algorithm for solving QMCTP in the polynomial-time solvable case. [ABSTRACT FROM AUTHOR]

A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν ( H ) of H is the size of a maximum matching in H . A subset D of vertices of H is a dominating set of H if for every v ∈ V ∖ D there exists u ∈ D such that u and v lie in an hyperedge of H . The cardinality of a minimum dominating set of H is the domination number of H , denoted by γ ( H ) . It was proved that γ ( H ) ≤ ( r − 1 ) ν ( H ) for r -uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ ( H ) = ν ( H ) have been characterized. In this paper we generalize the inequality γ ( H ) ≤ ( r − 1 ) ν ( H ) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ ( H ) = ( r − 1 ) ν ( H ) . [ABSTRACT FROM AUTHOR]

Given a graph G and a non-negative integer h , the h -restricted connectivity of G , denoted by κ h ( G ) , is defined as the minimum size of a set X of nodes in G ( X ⊂ V ( G ) ) such that G − X is disconnected, and the degree of each component in G − X is at least h . The h -restricted connectivity measure is a generalization of the traditional connectivity measure, and it improves the connectivity measurement accuracy. Moreover, studies have revealed that if a network possesses a restricted connectivity property, it is more reliable and demonstrates a lower node failure rate compared with other networks. The n -dimensional locally twisted cube L T Q n , which is a well-known interconnection network for parallel computing, is a variant of the hypercube Q n . Most studies have examined the h -restricted connectivity of networks under the conditions of h = 1 or h = 2 . This paper examines a generalized h -restricted connectivity measure for n -dimensional locally twisted cube and reveals that κ h ( L T Q n ) = 2 h ( n − h ) for 0 ≤ h ≤ n − 2 . [ABSTRACT FROM AUTHOR]

Let G be a cubic graph with a perfect matching. An edge e of G is a forcing edge if it is contained in a unique perfect matching M , and the perfect matching M is called uniquely forced . In this paper, we show that a 3-connected cubic graph with a uniquely forced perfect matching is generated from K 4 via Y → Δ -operations, i.e., replacing a vertex by a triangle, and further a cubic graph with a uniquely forced perfect matching is 2-connected and contains a triangle. Our result generalizes a previous result of Jiang and Zhang (2011). The unique 3-edge-coloring conjecture asserts that a Petersen-minor-free cubic graph with a unique 3-edge-coloring must contain a triangle. Our result verifies that the unique 3-edge-coloring conjecture holds for a subfamily of uniquely 3-edge-colorable cubic graphs, namely cubic graphs with uniquely forced perfect matching. [ABSTRACT FROM AUTHOR]

V -order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), themselves generalizations of Lyndon words. V -order has recently been proposed as an alternative to lexicographic order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows–Wheeler transform. Efficient V -ordering of strings thus becomes a matter of considerable interest. In this paper we discover several new combinatorial properties of V -order, then explore the computational consequences; in particular, a fast, simple on-line V -order comparison algorithm that requires no auxiliary data structures. [ABSTRACT FROM AUTHOR]

In this paper we study vector joint majorization for comparing m -tuple and n -tuple of pairs in the Cartesian product of two real linear spaces. We show a Sherman type inequality for a vector-valued ≤ C -convex function f , where ≤ C is a cone ordering. We also prove a Hardy–Littlewood–Pólya–Karamata type theorem for f . As applications, we generalize Csiszár–Körner’s inequality for f -divergence of two n -tuples of positive numbers. In doing so, we employ n -tuples of pairs of positive linear maps and positive operators on a Hilbert space. [ABSTRACT FROM AUTHOR]

Recently Mansour and Shattuck studied ( k , a ) -paths and gave formulas that related the total number of humps in all ( k , a ) -paths to the number of super ( k , a ) -paths. These results generalized earlier results of Regev on Dyck paths and Motzkin paths. Their proofs are based on generating functions and they asked for bijective proofs for their results. In this paper we first give bijective proofs of Mansour and Shattuck’s results, then we extend our study to ( n , m ) -Dyck paths. We give a bijection that relates the total number of peaks in all ( n , m ) -Dyck paths to certain free ( n , m ) -paths when n and m are coprime. From this bijection we get the number of ( n , m ) -Dyck paths with exactly j peaks, which is a generalization of the well-known result that the number Dyck paths of order n with exactly j peaks is the Narayana number 1 k n − 1 k − 1 n k − 1 . [ABSTRACT FROM AUTHOR]

The generalized Fibonacci cube Q d ( f ) is the graph obtained from the d -cube Q d by removing all vertices that contain a given binary word f as a factor; the generalized Lucas cube Q d ( f ↽ ) is obtained from Q d by removing all the vertices that have a circulation containing f as a factor. In this paper the Wiener index of Q d ( 1 s ) and the Wiener index of Q d ( 1 s ↽ ) are expressed as functions of the order of the generalized Fibonacci cubes. For the case Q d ( 111 ) a closed expression is given in terms of Tribonacci numbers. On the negative side, it is proved that if for some d , the graph Q d ( f ) (or Q d ( f ↽ ) ) is not isometric in Q d , then for any positive integer k , for almost all dimensions d ′ the distance in Q d ′ ( f ) (resp. Q d ′ ( f ↽ ) ) can exceed the Hamming distance by k . [ABSTRACT FROM AUTHOR]

A subset F ⊂ V(G) is called a decycling set if the subgraph G−F is acyclic. The minimum cardinality of a decycling set is called the decycling number of G, which is proposed first by Beineke and Vandell (1997). We use ∇(Pn, k) to denote the decycling number of the generalized Petersen graphs Pn, k. This paper proves that ... [ABSTRACT FROM AUTHOR]

In this paper, we prove that if a graph G is diamond-free, then the competition number of G is bounded above by 2 + 1/2 ∑v∈Vh(G) (θV(NG(v))−2) where Vh(G) is the set of nonsimplicial vertices of G. This result generalizes Opsut's result for line graphs. We also show that the upper bound holds for certain graphs which might have diamonds. As a matter of fact, we go further to a conjecture that the above upper bound holds for the competition number of any graph, which leads to a natural generalization of Opsut's conjecture. [ABSTRACT FROM AUTHOR]

The degree diameter problem involves finding the largest graph (in terms of the number of vertices) subject to constraints on the degree and the diameter of the graph. Beyond the degree constraint there is no restriction on the number of edges (apart from keeping the graph simple) so the resulting graph may be thought of as being embedded in the complete graph. In a generalization of this problem, the graph is considered to be embedded in some connected host graph, in this paper the honeycomb network. We consider embedding the graph in the k -dimensional honeycomb grid and provide upper and lower bounds for the optimal graph. The particular cases of dimensions 2 and 3 are examined in detail. [ABSTRACT FROM AUTHOR]

In the universally quickest transshipment problem, we are given a network with a transit time function on its arc set. The goal is to minimize the time when the last supply reaches the sink and to maximize the amount of supplies which have reached the sink at every time step. In this paper, we consider this problem in a class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time, and present a polynomial-time algorithm for this case. [ABSTRACT FROM AUTHOR]