Search

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]

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 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]

We study sequences of optimal walks of a growing length in weighted digraphs, or equivalently, sequences of entries of max-algebraic matrix powers with growing exponents. It is known that these sequences are eventually periodic when the digraphs are strongly connected. The transient of such periodicity depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that some bounds on the indices of periodicity of (unweighted) digraphs, such as the bounds of Wielandt, Dulmage–Mendelsohn, Schwarz, Kim and Gregory–Kirkland–Pullman, apply to the weights of optimal walks when one of their ends is a critical node. [ABSTRACT FROM AUTHOR]

Abstract: For two vertices and in a strong oriented graph , the strong distance between and is the minimum size (the number of arcs) of a strong sub-digraph of containing and . For a vertex of , the strong eccentricity is the strong distance between and a vertex farthest from . The strong radius is the minimum strong eccentricity among the vertices of , and the strong diameter is the maximum strong eccentricity among the vertices of . An orientation of a graph is said to be a strongly self-centered orientation of if . In this paper, we obtain some conditions for complete -partite graphs to have strongly self-centered orientations. Our results generalize a result on tournaments in Chartrand et al. (1999). [Copyright &y& Elsevier]

Abstract: In this paper we analyse the generalization performance of a type of binary classifier defined on the unit cube. This classifier combines some of the aspects of the standard methods that have been used in the logical analysis of data (LAD) and geometric classifiers, with a nearest-neighbor paradigm. We assess the predictive performance of the new classifier in learning from a sample, obtaining generalization error bounds that improve as a measure of ‘robustness’ of the classifier on the training sample increases. [Copyright &y& Elsevier]

Abstract: A subfamily of -trees, the -path graphs generalize path graphs in the same way -trees generalize trees. This paper presents a code for unlabeled -path graphs. The effect of structural properties of the family on the code is investigated, leading to the solution of two problems: determining the exact number of unlabeled -path graphs with vertices and generating all elements of the family. [Copyright &y& Elsevier]

Abstract: Let be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for is a subset of the rooms such that each vertex of is in exactly one room in . Given a room-partitioning for , the exchange algorithm walks from room to room until it finds a second different room-partitioning . In fact, this algorithm generalizes the Lemke–Howson algorithm for finding a Nash equilibrium for two-person games. In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs. [Copyright &y& Elsevier]

Abstract: The excessive -index of a graph , denoted by , is the minimum number of matchings of size needed to cover the edge-set of . We set if such a cover does not exist and we call a graph -coverable if its excessive -index is finite. Obviously and it is easy to prove for a -coverable graph that holds, where denotes the chromatic index of . The case is completely solved in Cariolaro and Fu (2009) [4]. In this paper we prove a general formula for computing the excessive -index of a tree and we conjecture a possible generalization for any value of . Furthermore, we prove that such a formula does not work for the excessive -index of an arbitrary graph. [Copyright &y& Elsevier]

Abstract: A graph is a unipolar graph if there exists a partition such that is a clique and induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs such that either or the complement of is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all -free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time , where is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in time, and for finding a maximum clique and a minimum proper coloring in time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs. [Copyright &y& Elsevier]

Abstract: Let be a graph of order and be a set of vertices. We call , -pancyclable, if for every with , there exists a cycle in such that . For any two nonadjacent vertices , of , we say that , are of distance 2 in , denoted by , if there is a path in connecting and such that . In this paper, we will prove that: Let be a 2-connected graph of order and be a subset of with . If for all pairs of vertices , of with , then is -pancyclable or else and is a spanning subgraph of , or else is even and is the complete bipartite graph , or else is even and is , or else and the structure of is well characterized. This generalizes a result of Benhocine and Wojda for the case when . [A. Benhocine, A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graph, J. Combin. Theory B 42 (1987) 167–180]. [Copyright &y& Elsevier]

Abstract: Let be a function that assigns to each vertex a subset of colors chosen from a set of colors. If for each vertex with , then is called a -rainbow dominating function ( RDF) of where . The weight of , denoted by , is defined as . Given a graph , the minimum weight among all weights of RDFs, denoted by , is called the -rainbow domination number of . Bres˘ar and S˘umenjak (2007) [5] gave an upper bound and a lower bound for . They showed that . In this paper, we propose a tight upper bound for when . [Copyright &y& Elsevier]

Abstract: Labeled graphs have applications in algorithms for reconstructing chains that have been split into smaller parts. Chain reconstruction is a common problem in biochemistry and bioinformatics, particularly for sequencing DNA or peptide chains. Labeled graphs (in the sense defined in this paper) have also the important structural property which allows to reduce the Hamiltonian path problem to Eulerian path problem. This work introduces a model and properties of a class of base-labeled graphs that unify the properties of labeled and free-labeled graphs (Błażewicz et al., 1999) [1]. It describes the basic relationships between those classes and some of their applications. It also introduces lexical graphs which are the superclass of de Bruijn graphs. Lexical graphs keep many properties of de Bruijn graphs which have a wide area of applications e.g. in mathematics, electronics and computing sciences. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the generalized ideal based zero divisor graph of a poset , denoted by . A representation theorem is obtained for generalized zero divisor graphs. It is proved that a graph is complete -partite with if and only if it is a generalized zero divisor graph of a poset. As a consequence of this result, we prove a form of a Beck’s Conjecture for generalized zero divisor graphs of a poset. Further, it is proved that a generalized zero divisor graph of a section semi-complemented poset with respect to the ideal is a complete graph. [Copyright &y& Elsevier]

Abstract: Let be the set of connected simple -vertex graphs with minimum vertex degree . The Randić index of a graph is defined by: , where is the degree of vertex and the summation extends over all edges of . In this paper we prove for the conjecture of Aouchiche and Hansen about the graphs in for which the Randić index attains its minimum value. We show that the extremal graphs are complete split graphs , which have only two degrees, i.e. degree and degree , and the number of vertices of degree is , while the number of vertices of degree is . At the end we generalize our results to graphs with prescribed maximum degree . [Copyright &y& Elsevier]

Abstract: In this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max -Fire where firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to . We also study the related decision problem -Fire that asks whether all the vertices in can be saved using firefighters at each time step. We show that -Fire is NP-complete for trees of maximum degree even when is the set of leaves. Using this last result, we prove the NP-hardness of Max -Fire for trees of maximum degree even when is the set of all vertices. On the positive side, we give a polynomial-time algorithm for solving -Fire and Max -Fire on trees of maximum degree when the fire breaks out at a vertex of degree at most . Moreover, we present a polynomial-time algorithm for the Max -Fire problem (and the corresponding weighted version) for a subclass of trees, namely -caterpillars. Finally, we observe that the minimization version of Max -Fire is not -approximable on trees for any and if . [Copyright &y& Elsevier]

Abstract: A quasi-hamiltonian path in a semicomplete multipartite digraph is a path which visits each maximal independent set (also called a partite set) of at least once. This is a generalization of a hamiltonian path in a tournament. In this paper we investigate the complexity of finding a quasi-hamiltonian path, in a given semicomplete multipartite digraph, from a prescribed vertex to a prescribed vertex as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices . While both of these problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is NP-complete and describe a polynomial algorithm for the latter problem. [Copyright &y& Elsevier]

Abstract: A coloring of a graph is a -coloring if in every color class there is a vertex whose neighborhood intersects every other color class. The -chromatic number of , denoted , is the greatest integer such that admits a -coloring with colors. A graph is tight if it has exactly vertices of degree , where is the largest integer such that has at least vertices of degree at least . Determining the -chromatic number of a tight graph is NP-hard even for a connected bipartite graph Kratochvil et al. (2002) [18]. In this paper we show that it is also NP-hard for a tight chordal graph. We also show that the -chromatic number of a split graph can be computed in polynomial time. We then define the -closure and the partial -closure of a tight graph, and use these concepts to give a characterization of tight graphs whose -chromatic number is equal to . This characterization is used to propose polynomial-time algorithms for deciding whether for tight graphs that are complement of bipartite graphs, -sparse and block graphs. We also generalize the concept of pivoted tree introduced by Irving and Manlove (1999) [13] and show its relation with the -chromatic number of tight graphs. [Copyright &y& Elsevier]

Abstract: In this paper we give a simple characterization of the Laplacian spectra of a family of graphs as the eigenvalues of symmetric tridiagonal matrices. In addition, we apply our result to obtain upper and lower bounds for the Laplacian-energy-like invariant of these graphs. The class of graphs considered are obtained from copies of modified generalized Bethe trees (obtained by joining the vertices at some level by paths), identifying their roots with the vertices of a regular graph or a path. [Copyright &y& Elsevier]

Abstract: The whist tournament problem has attracted the interests of many design theorists for over a century. To construct -cyclic whist tournaments, the concept of -cyclic patterned starter whist tournaments was introduced. The research on -cyclic patterned starter whist tournaments dates back to 1954. Although considerable progress has been made in the last decade or so, less has been made about the existence of -cyclic patterned starter whist tournaments, despite the efforts of many authors. In this paper, we will first provide two new nonexistence results for -cyclic patterned starter whist tournaments. Then, we will propose a general recursive construction, i.e., a frame construction, for -cyclic patterned starter whist tournaments. As a consequence, we are able to unify many known constructions for -cyclic patterned starter whist tournaments. The known existence results of such designs are then extended. [Copyright &y& Elsevier]

Abstract: Pooling designs are standard experimental tools in many biotechnical applications. It is well-known that all famous pooling designs are constructed from mathematical structures by the “containment matrix” method. In particular, Macula’s designs (resp. Ngo and Du’s designs) are constructed by means of the containment relation of subsets (resp. subspaces) in a finite set (resp. vector space). In [J. Guo, K. Wang, A construction of pooling designs with high degree of error correction, J. Combin. Theory Ser. A 118 (2011) 2056–2058], we generalized Macula’s designs and obtained a family of pooling designs with higher degree of error correction. In this paper we consider, as a generalization of Ngo and Du’s designs, -analogue of the above designs, and obtain a family of pooling designs with surprisingly high degree of error correction. Our designs and Ngo and Du’s designs have the same numbers of items and pools, but the error-tolerance property of our design is much better than that of Ngo and Du’s designs when the dimension of the space is large enough. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the concept of -power domination which is a common generalization of domination and power domination. We extend several known results for power domination to -power domination. Concerning the complexity of the -power domination problem, we first show that deciding whether a graph admits a -power dominating set of size at most is NP-complete for chordal graphs and for bipartite graphs. We then give a linear algorithm for the problem on trees. Finally, we propose sharp upper bounds for the power domination number of connected graphs and of connected claw-free -regular graphs. [Copyright &y& Elsevier]

Abstract: The matching preclusion number of an even graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. The conditional matching preclusion number of an even graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and no perfect matchings. In this paper we study this problem for the tori by proving matching preclusion and conditional matching preclusion results of the Cartesian products of graphs involving cycles. Our results generalize the one given for -ary -cube by Wang et al. (2010) as well as provide classification for optimal conditional matching preclusion sets for these graphs. [Copyright &y& Elsevier]

Abstract: This paper introduces a new generalized version of the Traveling Salesman Problem in which nodes belong to various color classes and each color class must be visited as an entity. We distinguish the cases of the problem for which the colors are either pre-assigned or can be selected from a given subset of colors. We establish computational complexity and provide concise formulations for the problems that lend themselves to derive tight lower bounds. Exact solutions for special cases and a two-phase heuristic for the general case are provided. Worst case performance and asymptotic performance of the heuristic are analyzed and the effectiveness of the proposed heuristic in solving large industrial size problems is empirically demonstrated. [Copyright &y& Elsevier]