Search

Abstract: The concept of labelled stratified graph (LSG) was introduced in Ţăndăreanu (Knowledge Inform. Syst. 2(4) (2000) 438) in connection with that of knowledge base with output (KBO). The aim of this paper is to present a distinct facet of this concept. We prove several algebraic properties for LSGs and we conclude that a LSG can be used independently of a KBO. In order to realize this aim we define a partial order on the set of all LSGs over a labelled graph G, an equivalence relation on and a partial order on the factor set. The set endowed with becomes a join semilattice with greatest element. Each equivalence class contains an unique LSG, which is named distinguished representative of C. This is the least element of. Particularly we obtain the distinguished representative for the supremum of two classes (DRS) and the greatest distinguished LSG (the least LSG of the greatest element of, denoted GD). Two applications are presented, one for DRS and one for GD. Several opens problems are briefly exposed in the last section. [Copyright &y& Elsevier]

In this paper, we consider the homogeneous m -machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k -schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m -machine scheduling problem. [ABSTRACT FROM AUTHOR]

Let r ≥ 2 and r be even. An r -hypergraph G on n vertices is called odd-colorable if there exists a map φ : [ n ] → [ r ] such that for any edge { j 1 , j 2 , … , j r } of G , we have φ ( j 1 ) + φ ( j 2 ) + ⋅ ⋯ ⋅ + φ ( j r ) ≡ r ∕ 2 ( mod r ) . In this paper, we first determine that, if r = 2 q ( 2 t + 1 ) and n ≥ 2 q ( 2 q − 1 ) r , then the maximum chromatic number in the class of the odd-colorable r -hypergraphs on n vertices is 2 q , which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r -hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum S p e c ( L ( G ) ) and the signless Laplacian spectrum S p e c ( Q ( G ) ) of an r -hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r ⁄ ≡ 0 ( m o d 4 ) of a question raised in Shao et al. (2015) about whether S p e c ( L ( G ) ) = S p e c ( Q ( G ) ) implies that L ( G ) and Q ( G ) have the same H-spectrum. [ABSTRACT FROM AUTHOR]

This paper provides new results on the application of semidefinite optimization to satisfiability by studying the connection between semidefinite optimization and minimal unsatisfiability. We use a semidefinite least squares problem to assign weights to the clauses of a propositional formula in conjunctive normal form. We then show that these weights are a measure of the necessity of each clause in rendering the formula unsatisfiable, the weight of a necessary clause is strictly greater than the weight of any unnecessary clause. In particular, we show the following results: first, if a formula is minimal unsatisfiable, then all of its clauses have the same weight; second, if a clause does not belong to any minimal unsatisfiable subformula, then its weight is zero. An additional contribution of this paper is a demonstration of how the infeasibility of a semidefinite optimization problem can be tested using a semidefinite least squares problem by extending an earlier result for linear optimization. The connection between the semidefinite least squares problem and Farkas’ Lemma for semidefinite optimization is also discussed. [ABSTRACT FROM AUTHOR]

This is a survey or exposition of a particular collection of results and open problems involving snarks — simple “cubic” (3-valent) graphs for which, for nontrivial reasons, the edges cannot be 3-colored. The results and problems here are rooted in a series of papers by László Kászonyi that were published in the early 1970s. The problems posed in this survey paper can be tackled without too much specialized mathematical preparation, and in particular seem well suited for interested undergraduate mathematics students to pursue as independent research projects. This survey paper is intended to facilitate research on these problems. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the edge-magicness of graphs with equal size and order, and we use such graphs and digraph products in order to construct labelings of different classes and of different graphs. We also study super edge-magic labelings of -regular graphs with exactly two components and their implications to other labelings. The strength of the paper lays on the techniques used, since they are not only used in order to provide labelings of many different types of families of graphs, but they also show interesting relations among well studied types of labelings. We are able to obtain, in this way, deep results relating different types of labelings. [Copyright &y& Elsevier]

Abstract: In this paper, we study the basic homogeneous -machine scheduling problem where weakly dependent unit-time jobs have to be scheduled within the time windows between their release dates and due dates so that, for any subset of machines, the set of the time units at which at least one machine is busy, is in interval. We first introduce the notions of pyramidal structure, -hole, -matching, preschedule, -schedule and schedule for this problem. Then we provide a feasibility criteria for a preschedule. The key result of the paper is then to provide a structural necessary and sufficient condition for an instance of the problem to be feasible. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling -machine scheduling problem. [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]

Abstract: The generalized Petersen graph is an undirected graph on vertices with and . Fiorini claimed to have determined the crossing numbers of and showed all the values of for up to 14, except 12 unknown values. Lovrečič Saražin proved . Richter and Salazar found a gap in Fiorini’s paper, which invalidated his principal results about , and gave the correct proof for . In this paper, we show the crossing numbers of all for up to 16. [Copyright &y& Elsevier]

Abstract: Neighborhoods and neighborhood sequences play important roles in several branches of pattern analysis. In earlier papers in only certain special (e.g. periodic or octagonal) sequences were investigated. In this paper we study neighborhood sequences which are either ultimately periodic or allow at every neighborhood to do nothing at no cost. We give finite procedures and descriptive theoretical criteria for certain important (e.g. metrical) properties of the sequences. Our results are valid for several types of classical neighborhood sequences and for generated distance functions (e.g. octagonal and chamfer distances) which are widely applied in digital image processing. We conclude the paper by showing how our results contribute to the theory of distance transformations. [Copyright &y& Elsevier]

Abstract: The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers for subsequent queries of the form: “Given indices i, j, what is the index of the minimum value of ?” This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: “Given indices i and j, what is the maximum-sum segment of ?” We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper. [Copyright &y& Elsevier]

Abstract: Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311–320.] introduced -graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let and d be non-negative integers such that and is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an -graph. Liu and Yu''s Papee''s paper, the recursive relations for distinct parameters and d were presented and the impact of adding or deleting an edge also was discussed for the case . In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for -graphs in the general case . [Copyright &y& Elsevier]

Abstract: Digital planarity is defined by digitizing Euclidean planes in the three-dimensional digital space of voxels; voxels are given either in the grid-point or the grid-cube model. The paper summarizes results (also including most of the proofs) about different aspects of digital planarity, such as supporting or separating Euclidean planes, characterizations in arithmetic geometry, periodicity, connectivity, and algorithmic solutions. The paper provides a uniform presentation, which further extends and details a recent book chapter in [R. Klette, A. Rosenfeld, Digital Geometry—Geometric Methods for Digital Picture Analysis, Morgan Kaufmann, San Francisco, 2004]. [Copyright &y& Elsevier]

Abstract: A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59–73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such that is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that is a tree. [Copyright &y& Elsevier]

Abstract: In a finite dataset consisting of positive and negative observations represented as real valued -vectors, a positive (negative) pattern is an interval in with the property that it contains sufficiently many positive (negative) observations, and sufficiently few negative (positive) ones. A pattern is spanned if it does not include properly any other interval containing the same set of observations. Although large collections of spanned patterns can provide highly accurate classification models within the framework of the Logical Analysis of Data, no efficient method for their generation is currently known. We propose in this paper, an incrementally polynomial time algorithm for the generation of all spanned patterns in a dataset, which runs in linear time in the output; the algorithm resembles closely the Blake and Quine consensus method for finding the prime implicants of Boolean functions. The efficiency of the proposed algorithm is tested on various publicly available datasets. In the last part of the paper, we present the results of a series of computational experiments which show the high degree of robustness of spanned patterns. [Copyright &y& Elsevier]

Abstract: Known secure multi-party computation protocols are quite complex, involving non-trivial mathematical structures and sub-protocols. The purpose of this paper is to present a very simple approach to secure multi-party computation with straight-forward security proofs. This approach naturally yields protocols secure for mixed (active and passive) corruption and general (as opposed to threshold) adversary structures, confirming the previously proved tight bounds in a simpler framework. Due to their simplicity, the described protocols are well-suited for didactic purposes, which is a main goal of this paper. [Copyright &y& Elsevier]

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]

Given a linear equation L , a set A of integers is L -free if A does not contain any ‘non-trivial’ solutions to L . This notion incorporates many central topics in combinatorial number theory such as sum-free and progression-free sets. In this paper we initiate the study of (parameterised) complexity questions involving L -free sets of integers. The main questions we consider involve deciding whether a finite set of integers A has an L -free subset of a given size, and counting all such L -free subsets. We also raise a number of open problems. [ABSTRACT FROM AUTHOR]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

The generalized Wiener polarity index of a graph G , denoted by W k ( G ) , is the number of unordered pairs of vertices that are at distance k in G. In this paper, we characterize the extremal trees with respect to the index among all trees of order n and diameter d , which partially answers a question of Bollobás and Tyomkyn (2012) and also generalizes some results of Deng et al. (2010). [ABSTRACT FROM AUTHOR]

For positive integers k and r , a ( k , r )-coloring of a graph G is a proper k -coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min { d , r } different colors. The r -hued chromatic number of a graph G , denoted by χ r ( G ) , is the smallest integer k such that G has a ( k , r ) -coloring. In Song et al. (2014), it is conjectured that if r ≥ 8 , then every planar graph G satisfies χ r ( G ) ≤ ⌈ 3 r 2 ⌉ + 1 . Wegner in 1977 conjectured that the above-mentioned conjecture holds when r = Δ ( G ) . This conjecture, if valid, would be best possible in some sense. In this paper, we prove that, if G is a planar graph and r ≥ 8 , then χ r ( G ) ≤ 2 r + 16 . [ABSTRACT FROM AUTHOR]

An edge-coloured path is rainbow if its edges have distinct colours. For a connected graph G , the rainbow connection number (resp. strong rainbow connection number ) of G is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by a rainbow path (resp. rainbow geodesic). These two graph parameters were introduced by Chartrand, Johns, McKeon, and Zhang in 2008. Krivelevich and Yuster generalised this concept to the vertex-coloured setting. Similarly, Liu, Mestre, and Sousa introduced the version which involves total-colourings. Dorbec, Schiermeyer, Sidorowicz, and Sopena extended the concept of the rainbow connection to digraphs. In this paper, we consider the (strong) total rainbow connection number of digraphs. Results on the (strong) total rainbow connection number of biorientations of graphs, tournaments, and cactus digraphs are presented. [ABSTRACT FROM AUTHOR]

An arc-coloured digraph D is alternating if whenever ( u , v ) and ( v , w ) are arcs in D they are of different colours. In an arc coloured digraph D , a subset K ⊂ V ( D ) of vertices of D is a kernel by alternating paths (or alternating kernel ) if it is absorbent and independent by directed alternating paths. In this paper we prove sufficient conditions for the existence of alternating kernels in arc-coloured tournaments, quasi-transitive digraphs, and k -partite digraphs. [ABSTRACT FROM AUTHOR]

In this paper we continue studying the independent transversal domination number in a graph, i.e., the cardinality of a smallest dominating set which intersects each maximum independent set. As our main result, we prove two upper bounds on the independent transversal domination number in terms of the order and minimum degree of a graph. [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]

The spectrum of a first order sentence is the set of all α such that G ( n , n − α ) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1 ∕ 2 and 3 ∕ 5 . [ABSTRACT FROM AUTHOR]

For a graph G , we denote by σ 2 ( G ) the minimum degree sum of two non-adjacent vertices if G is non-complete; otherwise, σ 2 ( G ) = + ∞ . In this paper, we prove the following two results: (i) If s 1 , s 2 ≥ 2 are integers and G is a non-complete graph with σ 2 ( G ) ≥ 2 ( s 1 + s 2 + 1 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least s i + 1 with σ 2 ( H i ) ≥ 2 s i − 1 . (ii) If s 1 , s 2 ≥ 2 are integers and G is a triangle-free graph of order at least 3 with σ 2 ( G ) ≥ 2 ( s 1 + s 2 ) − 1 , then G contains two vertex-disjoint subgraphs H 1 and H 2 such that each H i is a graph of order at least 2 s i with σ 2 ( H i ) ≥ 2 s i − 1 . By using this result, we also give some corollaries concerning degree conditions for the existence of k vertex-disjoint cycles. [ABSTRACT FROM AUTHOR]

The allowed patterns of a map are those permutations in the same relative order as the initial segments of orbits realized by the map. In this paper, we characterize and provide enumerative bounds for the allowed patterns of signed shifts, a family of maps on infinite words. [ABSTRACT FROM AUTHOR]

An edge-coloured connected graph G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k colours then G is called k -rainbow connected. The rainbow connection number of G , denoted by rc ( G ) , is the minimum k such that G is k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G is a connected graph of order n and size m with n − 2 2 + 2 ≤ m ≤ n − 1 2 , then 2 ≤ rc ( G ) ≤ 3 . In this paper we will present sufficient conditions for graphs G of this size to fulfil rc ( G ) = 2 depending on vertex degrees. [ABSTRACT FROM AUTHOR]

Abstract: How large can a family be if it does not contain with ? Our aim in this paper is to show that any such family has size at most . This is tight up to a multiplicative constant of 2. We also obtain similar results for families with , showing that they satisfy , where is a constant depending only on . [Copyright &y& Elsevier]

Abstract: Wegner conjectured that for each planar graph with maximum degree at least 4, if , and if . Let be a planar graph without 4-cycles. In this paper, we discuss the -labelling of , and show that , where and are positive integers with . As a corollary, and . [Copyright &y& Elsevier]

Abstract: Let be a connected regular graph. Denoted by and the total graph and Kirchhoff index of , respectively. This paper is to point out that Theorem 3.7 and Corollary 3.8 from “Kirchhoff index in line, subdivision and total graphs of a regular graph” [X. Gao, Y.F. Luo, W.W. Liu, Kirchhoff index in line, subdivision and total graphs of a regular graph, Discrete Appl. Math. 160(2012) 560–565] are incorrect, since the conclusion of a lemma is essentially wrong. Moreover, we first show the Laplacian characteristic polynomial of , where is a regular graph. Consequently, by using , we give an expression on and a lower bound on of a regular graph , which correct Theorem 3.7 and Corollary 3.8 in Gao et al. (2012) [2]. [Copyright &y& Elsevier]

Abstract: The -ary -cube is one of the most popular interconnection networks for parallel and distributed systems. Strong matching preclusion that additionally permits more destructive vertex faults in a graph is a more extensive form of the original matching preclusion that assumes only edge faults. In this paper, we establish the strong matching preclusion number and all minimum strong matching preclusion sets for -ary -cubes with and . [Copyright &y& Elsevier]

Abstract: For a connected graph , an edge set is a -restricted edge cut if is disconnected and every component of has at least vertices. The -restricted edge connectivity of , denoted by , is defined as the cardinality of a minimum -restricted edge cut. Let . is -optimal if . In 2004, Hellwig and Volkmann gave a sufficient condition for -optimality in graphs of diameter 2. In this paper, we extend the result and give a similar sufficient condition for -optimality in graphs of diameter 2 with . [Copyright &y& Elsevier]

Abstract: Let be the graph obtained from by adding a new vertex corresponding to each edge of and by joining each new vertex to the end vertices of the corresponding edge, and be the graph obtained from by inserting a new vertex into every edge of and by joining by edges those pairs of these new vertices which lie on adjacent edges of . In this paper, we determine the Laplacian polynomials of and of a regular graph ; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs. [Copyright &y& Elsevier]

Abstract: Compound distributions come up in many applications (telecommunication, hydrology, insurance, etc.), where some of the typical problems are of optimization type. The log-concavity property is paramount in these respects to ensure convexity. In this paper, we prove the log-concavity of some compound Poisson and other compound distributions. [Copyright &y& Elsevier]

Abstract: A proper edge coloring of a graph is if there is no bichromatic cycle in . The acyclic chromatic index of , denoted , is the least number of colors such that has an acyclic -edge-coloring. In this paper, it is shown that if is a planar graph with girth at least 5 and maximum degree , then . Moreover, if , then . [Copyright &y& Elsevier]

Abstract: In this paper, we study the following two hypercube coloring problems: given and , find the minimum number of colors, denoted as (resp. ), needed to color the vertices of the -cube such that any two vertices with Hamming distance at most (resp. exactly ) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that for any odd number , and give two upper bounds on . The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small . Furthermore, we derive an inequality on and . [Copyright &y& Elsevier]

Abstract: Let be the set of faulty nodes in an -dimensional folded hypercube with . In this paper, we show that if , then every edge of lies on a fault-free cycle of every even length from to , and if and is even, then every edge of lies on a fault-free cycle of every odd length from to . [Copyright &y& Elsevier]

Abstract: A finite Sturmian word is a balanced word over the binary alphabet , that is, for all subwords and of of equal length, , where and denote the number of occurrences of the letter in and , respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity. [Copyright &y& Elsevier]

Abstract: Let be positive integers. A -edge-colored graph is -e.c. or -existentially closed if for any disjoint sets of vertices with , there is a vertex not in such that all edges from this vertex to the set are colored by the -th color. In this paper, we give an explicit construction of a -e.c. graph of polynomial order. [Copyright &y& Elsevier]

Abstract: Let be a graph, a vertex labeling induces an edge labeling defined by for each . For each, define and . We call friendly if . The full friendly index set of is the set of all possible values of , where is friendly. In this paper, we study the full friendly index sets of some standard graphs such as the complete graph , the cycle , fans and and the Cartesian product of and i.e. . [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [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: The crossing resolution of a geometric graph is the minimum crossing angle at which any two edges cross each other. In this paper, we present upper and lower bounds to the crossing resolution of the complete geometric graphs. [Copyright &y& Elsevier]

Abstract: Given a graph , a vertex colouring of is -frugal if no colour appears more than times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind et al. (1997)  studied proper -frugal colourings and Yuster (1998)  studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study. [Copyright &y& Elsevier]

Abstract: An edge-coloring of a graph with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs. [Copyright &y& Elsevier]

Abstract: Since Cohen introduced the competition graph in 1968, the competition graph has been studied widely and many variations of it have been discussed. In 2000, Cho, Kim and Nam defined and studied the -step competition graph and computed the 2-step competition numbers of paths and cycles. Recently, Ho gave bounds for the -step competition numbers of paths and cycles. In this paper we continue to study the -step competition numbers of paths and cycles, partially improve the results of Ho on the upper bounds of the -step competition numbers of paths and cycles, and show that a conjecture posed by Ho is not true. [Copyright &y& Elsevier]

Abstract: Given an edge-weighted graph and a list of source–sink pairs of terminal vertices of , the minimum multicut problem consists in selecting a minimum weight set of edges of whose removal leaves no path from the th source to the th sink, for each . Few tractable special cases are known for this problem. In this paper, we give a simple polynomial-time algorithm solving it in undirected planar graphs where (I) all the terminals lie on the outer face and (II) there is a bounded number of terminals. [Copyright &y& Elsevier]