Search

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]

Abstract: This paper analyzes the predictive performance of standard techniques for the ‘logical analysis of data’ (LAD), within a probabilistic framework. It does so by bounding the generalization error of related polynomial threshold functions in terms of their complexity and how well they fit the training data. We also quantify the predictive accuracy in terms of the extent to which there is a large separation (a ‘large margin’) between (most of) the positive and negative observations. [Copyright &y& Elsevier]

Abstract: The vertex Padmakar–Ivan index of a graph , denoted by , is the sum over all edges of of the number of vertices which are not equidistant from and . Similarly, edge Padmakar–Ivan index of a graph , denoted by , is the sum over all edges of of the number of edges which are not equidistant from and . In this paper, and of the generalized hierarchical product of two connected graphs are obtained. Using the results obtained here, some known results are deduced as corollaries. Finally, we obtain the and of the zig-zag polyhex nanotube and hexagonal chain . [Copyright &y& Elsevier]

Abstract: In this paper, we give a new interpretation of the generalized Fibonacci numbers and the generalized Lucas numbers also with respect to the total number of -matchings in the corona of special graphs. In special cases, we obtain the graph interpretation of the generalized Pell numbers and generalized Pell–Lucas numbers. [Copyright &y& Elsevier]

Abstract: For a strongly connected digraph the restricted arc-connectivity is defined as the minimum cardinality of an arc-cut over all arc-cuts satisfying that has a non-trivial strong component such that contains an arc. In this paper we prove that a generalized -cycle is -optimal if , where is the semigirth of and . Further we show that the -iterated line digraph is -optimal if for . We improve these results for large enough and we also improve known results on super- for -cycles with . [Copyright &y& Elsevier]

Abstract: The Generalized Bin Packing Problem (GBPP) is a recently introduced packing problem where, given a set of bins characterized by volume and cost and a set of items characterized by volume and profit (which also depends on bins), we want to select a subset of items to be loaded into a subset of bins which maximizes the total net profit, while satisfying the volume and bin availability constraints. The total net profit is given by the difference between the total profit of the loaded items and the total cost of the used bins. In this paper, we consider the stochastic version of the GBPP (S-GBPP), where the item profits are random variables to take into account the profit oscillations due to the handling operations for bin loading. The probability distribution of these random variables is assumed to be unknown. By using the asymptotic theory of extreme values a deterministic approximation for the S-GBPP is derived. [Copyright &y& Elsevier]

Abstract: Given a graph with nonnegative costs defined on edges, a positive integer , and a collection of terminal sets , where each is a subset of , the Generalized -Multicut problem asks to find a set of edges at the minimum cost such that its removal from cuts at least terminal sets in . A terminal subset is cut by if all terminals in are disconnected from one another by removing from . This problem is a generalization of the -Multicut problem and the Multiway Cut problem. The famous Densest -Subgraph problem can be reduced to the Generalized -Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an -approximation algorithm for the Generalized -Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP-hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give -approximation for the Generalized -Multicut problem in undirected graphs and -approximation for the -Forest problem. [Copyright &y& Elsevier]

Abstract: A nonbinary Ford sequence is a de Bruijn sequence generated by simple rules that determine the priorities of what symbols are to be tried first, given an initial word of size which is the order of the sequence being generated. This set of rules is generalized by the concept of a preference function of span , which gives the priorities of what symbols to appear after a substring of size is encountered. In this paper, we characterize preference functions that generate full de Bruijn sequences. More significantly, we establish that any preference function that generates a de Bruijn sequence of order also generates de Bruijn sequences of all orders higher than , thus making the Ford sequence no special case. Consequently, we define the preference function complexity of a de Bruijn sequence to be the least possible span of a preference function that generates this de Bruijn sequence. [Copyright &y& Elsevier]

Abstract: In this paper we deal with upper bounds on the -number of graphs of the form , where is one of the standard graph products—the direct, Cartesian, strong, and the lexicographic product. -labelling of products of graphs has been investigated by a number of authors, especially in connection with the well-known conjecture , where is the maximum degree of a graph . Up to some degenerate cases, this conjecture was verified for the Cartesian and the lexicographic product by Shao and Yeh (2005) , and for the direct and the strong product by Klavžar and Špacapan (2006)  and by Shao et al. (2008) . If one of the factors of the Cartesian or the direct product has maximum degree one, only higher upper bounds than the one following from the conjecture are currently known. We derive alternative upper bounds on the -number of graphs for the standard products mentioned above, with the role of the maximum degree taken over by the -number of the graph . Methods include lifts along graph covering projections and labellings of -sums constructed by Georges and Mauro (2002) . In most cases, our upper bounds are tighter than those currently known. [Copyright &y& Elsevier]

Abstract: In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall’s marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum -quasi-matching (that is a set of edges in a bipartite graph such that in one set of the bipartition every vertex has at least incident edges from , where is a so-called need mapping, while on the other side of the bipartition the distribution of degrees with respect to is lexicographically minimum). We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement: the optima of any component-based strictly convex cost function on any subset of -sphere in are precisely the lexicographically minimal elements of this subset. We also present an application in designing optimal CDMA-based wireless sensor networks. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is an assignment of nonnegative integers to the vertices of such that if vertices and are adjacent, , and if and are at distance two, . The -number of is the minimum span over all -labelings of . A generalized Petersen graph (GPG) of order consists of two disjoint copies of cycles on vertices together with a perfect matching between the two vertex sets. By presenting and applying a novel algorithm for identifying GPG-specific isomorphisms, this paper provides exact values for the -numbers of all GPGs of orders 9, 10, 11, and 12. For all but three GPGs of these orders, the -numbers are 5 or 6, improving the recently obtained upper bound of 7 for GPGs of orders 9, 10, 11, and 12. We also provide the -numbers of several infinite subclasses of GPGs that have useful representations on Möbius strips. [Copyright &y& Elsevier]

Abstract: Techniques for the logical analysis of binary data have successfully been applied to non-binary data which has been ‘binarized’ by means of cutpoints; see Boros et al. (1997, 2000) . In this paper, we analyze the predictive performance of such techniques and, in particular, we derive generalization error bounds that depend on how ‘robust’ the cutpoints are. [Copyright &y& Elsevier]

Abstract: For a graph , denotes the minimum degree of . In 1971, Bondy proved that, if is a 2-connected graph of order and for each pair of non-adjacent vertices , in , then is pancyclic or . In 2006, Wu et al. proved that, if is a 2-connected graph of order and for each pair of non-adjacent vertices , of in , then is pancyclic or . In this paper, we introduce a new condition which generalizes two conditions of degree sum and neighborhood union and prove that, if is a 2-connected graph of order and for any three vertices , , of and or in , then is pancyclic or . This result also generalizes the above two results. [Copyright &y& Elsevier]

Abstract: Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in : Suppose a graph contains one defective edge . Find the endpoints of by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of or not. What is then the minimum number of tests, which are needed in the worst case to identify ? In Gerzen (2009) , this problem was partially solved by deriving sharp lower and upper bounds for . In addition, it was proved that the determination of is an NP-complete problem. Among others, it was shown that the inequality holds for graphs with 2-complexity and the edge set . In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization. [Copyright &y& Elsevier]

Abstract: Consensus trees have been used routinely in systematic biology for over 30 years with the majority-rule consensus tree among the most popular. In this paper we give axioms that characterize a new consensus function, called majority-rule (+), that is based on a generalization of majority-rule to the supertree case. In addition, two other related consensus functions are characterized. [Copyright &y& Elsevier]

Abstract: Proposing them as a general framework, Liu and Yu (2001) introduced -graphs to unify the concepts of deficiency of matchings, -factor-criticality and -extendability. Let be a graph and let and be non-negative integers such that and is even. If on deleting any vertices from the remaining subgraph of contains a -matching and each -matching can be extended to a defect- matching in , then is called an -graph. In this paper, we obtain more properties of -graphs, in particular the recursive relations of -graphs for distinct parameters and . Moreover, we provide a characterization for maximal non--graphs. [Copyright &y& Elsevier]

Abstract: Formal concept analysis has been a topic of interest for about two decades. The mathematical notion of concept has its origin in formal logic. However, the empirical notion of concept has evolved through its use in many different disciplines. In this paper, we generalize the mathematical notion of concept and investigate order-theoretic properties of concept hierarchies for the new notion of concept. [Copyright &y& Elsevier]