Search

Abstract: In 1998, C. Lütolf and F. Margot [C. Lütolf, F. Margot, A Catalog of minimally nonideal matrices, Math. Methods Oper. Res. 47 (1998) 221–241] defined the notion of Lehman matrices in order to classify minimally non-ideal clutters. In the paper [H. Shinohara, Thin Lehman Matrices Arising from Finite Groups, Linear Algebra and Appl. to appear], one of the authors defined the notion of 1-overlapped factorizations of finite group which produces an infinite family of Lehman matrices and proved many properties of 1-overlapped factors. In this paper, we characterize circulant thin Lehman matrices with small constant line sum and provide many useful properties of 1-overlapped factors of cyclic groups. [Copyright &y& Elsevier]

Abstract: This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth. [Copyright &y& Elsevier]

Abstract: This paper considers the Bicriteria Shortest Path Problem (BSP) with the two conflicting objectives, minimizing the transportation cost and the total travel time. Bicriteria Shortest Path Problems, are often NP-hard problems [P. Hansen, Bicriterion path problems. In: Multiple criteria decision making: theory and applications. Heidelberg: Springer, (1980):109-127], since obtaining the set of efficient solutions to a BSP problem is more difficult than solving the corresponding single-objective problem. This paper proposes a Bicriteria Genetic Algorithm approach to solve bicriteria shortest path problem. [ABSTRACT FROM AUTHOR]

Abstract: We determine a surprising class for which edge-colouring is NP-complete but whose graphs are all Type 1. The class of unichord-free graphs was recently studied by Trotignon and Vušković [N. Trotignon and K. Vušković. A structure theorem for graphs with no cycle with a unique chord and its consequences. To appear in J. Graph Theory. (Available online at http://www.comp.leeds.ac.uk/vuskovi/chord.ps.)] in the context of vertex-colouring. Machado, Figueiredo and Vušković [R. C. S. Machado, C. M. H. de Figueiredo, and K. Vušković. Chromatic index of graphs with no cycle with unique chord. In: Proc. of the ALIO/EUROWorkshop on Applied Optimization (2008). Full paper submitted to Theoret. Comput. Sci.] established the NP-completeness of edge-colouring unichord-free graphs. For the subclass of {square,unichord}-free graphs, an interesting complexity dicothomy holds [R. C. S. Machado, C. M. H. de Figueiredo, and K. Vušković. Chromatic index of graphs with no cycle with unique chord. In: Proc. of the ALIO/EUROWorkshop on Applied Optimization (2008). Full paper submitted to Theoret. Comput. Sci.]: if the maximum degree is 3, the edge-colouring is NP-complete, otherwise, the problem is polynomial. Subsequently, Machado and Figueiredo [R. C. S. Machado and C. M. H. de Figueiredo. Total chromatic number of chordless graphs. In: Proc. of the Cologne-Twente Workshop (2009). Full paper submitted to Discrete Appl. Math.] settled the validity of the Total-Colouring Conjecture for {square,unichord}-free graphs by proving that non-complete {square,unichord}-free graphs of maximum degree at least 4 are Type 1. In the present work, we prove that non-complete {square,unichord}-free graphs of maximum degree 3 are Type 1, establishing the polynomiality of total-colouring restricted to {square,unichord}-free graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a graph of order n and size m. A labeling of G is a bijective mapping , and we call the set of all labelings of G. For any graph G and any labeling , let . In this paper, we consider the S-Labeling problem, defined as follows: Given a graph G, find a labeling that minimizes . The S-Labeling problem has been shown to be NP-complete [S. Vialette, Packing of (0, 1)-matrices, Theoretical Informatics and Applications RAIRO 40 (2006), no. 4, 519–536]. We prove here basic properties of any optimal S-labeling of a graph G, and relate it to the Vertex Cover problem. Then, we derive bounds for , and we give approximation ratios for different families of graphs. We finally show that the S-Labeling problem is polynomial-time solvable for split graphs. Due to space constraints, proofs are totally absent from this paper. They will be available in its journal version. [Copyright &y& Elsevier]

Abstract: N.S. Bhave and B.Y. Bam [S. S. Kamath and Saroja R. Hebbar, Strong and weak Domination, Full sets and Domintion Balance in Semigraphs, Preprint], introduced the concept of middle end degree ((m, e)− degree) of a vertex in a semigraph. This paper is devoted to a particular type of a-domination in which the (m, e)− degree plays a part. A vertex u (m, e)-strong dominates another vertex v if u and v are adjacent and in the lexico graphic order. (m, e)- dominating sets and (m, e)- domination number are defined and studied in this paper. [Copyright &y& Elsevier]

Abstract: A notion of a balanced automorphism of a group was introduced in [J. Sirǎn and M. Skoviera. Regular maps from Cayley graphs. I. Balanced Cayley maps. Algebraic graph theory (Leibnitz, 1989). Discrete Math. 109 (1992), no. 1–3, 265–276] in order to study regular Cayley maps over finite groups. One of the open questions formulated in the paper was this: which finite abelian groups admit a balanced automorphism? The presented paper answers this question. [Copyright &y& Elsevier]

Abstract: Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L Graham, H.Pollack On the addressing problem for loop switching, Bell System Technol., J. 50 (1971) 2495–2519], and Djokovic̀ [D. Djokovic̀, Distance preserving subgraphs of the hypercubes, Journal of Combinatorial Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we prove that a subdivision of a complete graph of order , is a partial cube if and only if this one is isomorphic to , or there exist non-subdivided edges of adjacent to a common vertex in the subdivision and the other edges of are subdivided an odd number of times. [Copyright &y& Elsevier]

Abstract: Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [R.L Graham, H.Pollak On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495–2519] and Djokovic̀ [D. Djokovic̀, Distance preserving subgraphs of the hypercubes, J. Combin. Theory, Ser B41 (1973), 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specially, we deal with the case where this configuration is a connected graph of order 4 on one hand and the case where the configuration is a fan on the other hand. Finally, we conjecture that a subdivision of a complete graph of order is a partial cube if and only if this one is isomorphic to or there exists edges of adjacent to a common vertex in the subdivision and the other edges of contain odd added vertices. This proposition is true when the order . [Copyright &y& Elsevier]

Abstract: Symmetry of graphs has been extensively studied over the past 50 years by using automorphisms of graphs and group theory which have played an important role in graph, and promising and interesting results have been obtained [N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1993, C. Godsil, C. Royle, Algebraic graph theory, Springer-Verlag, London, 2001, G. Hahn, G. Sabidussi, Graph Symmetry (algebraic methods and application), Kluwer Academic Publishers, Dordrecht, 1997]. We introduced generalized symmetry of graphs and investigated it by using endomorphisms of graphs and semigroup theory. In this paper, I will survey some results we have achieved in recent years. The paper consists of the following sections. [1.] Introduction [2.] End-regular graphs [3.] Weakly transitive graphs [4.] Cayley graphs of semigroups [5.] Unretractive graphs [6.] Graphs and their endomorphism monoids. [Copyright &y& Elsevier]

Point set domination was introduced by E. Sampathkumar et al in the paper titled ‘POINT SET DOMINATION NUMBER OF A GRAPH’. A subset D of V(G) of a connected graph G is a point set dominating set (psd - set) of G if for every T ⊆ V - D there exists d ∈ D such that the subgraph < T ⨆ {d} > induced by T ⨆ {d} is connected. The point set domination number γp(G) is the cardinality of a minimum psd set. In this paper we define the following:i. A set D ⊆ V(G) is said to be a strong point set dominating set (spsd set) of G if for every T ⊆ V - D there exists a vertex d ∈ D such that the subgraph < T ⊆{d} > induced by T ⨆ {d} is connected and deg d ≥ deg t for all t ∈ T.ii. The cardinality of minimum spsd set is called the strong point set domination number and is denoted by γsp (G)iii. If A ⊆ V then N(A) = the set of all neighbours of vertices in A and N[A] = A⨆N(A).iv. For a complete block B, B+Δ is obtained by the adjunction of a vertex of deg Δ at each vertex of the block.v. ksp = max {∣B∣ - γsp (B)} where BG denote the set of all blocks of G. [Copyright &y& Elsevier]

A time-stamped graph is an undirected graph with a real number on each edge. Vertex u influences vertex v if there is an increasing path from u to v. The induced influence digraph of a time-stamped graph is the directed graph that records the influences. In this paper we study the realizability problem: Given a parameter value, does there exist a time-stamped graph whose induced influence digraph has the given parameter value? In particular, we solve this problem when the parameter is the number of arcs. Moreover, if the candidates for the time-stamped graphs are restricted to trees, then every realizable value can be achieved by a tree homeomorphic to K2 or K1,3. A number of other questions are also explored. The full version of this paper is submitted to a referreed journal. [Copyright &y& Elsevier]

In this paper, we extend a result due to R. B. Allan and R. C. Laskar on graphs whose independent domination numbers equal their domination numbers.We will consider finite simple graphs as treated in most of the standard text-books on Graph Theory (e.g., see D. B. West [1]).Let G = (V,E) be any graph and D ⊆ V. We let N(D) denote the set of all vertices adjacent to those in D; the vertices in N(D) are often called the neighbours of those in D. In particular, if D = {u} then N(D) is written simply as N(u) The set D is called a dominating set (or, simply a domset) of G if N(ν) ∩ D ≠  for every ν ∈ V - D and an independent domset is often called a kernel of G (see [2, 3, 4, 5]). We will denote by D(G) (Di(G)) the set of all domsets (kernels) in G If G is a finite graph then the least cardinality of a domset (kernel) of G is called its domination (independent domination) number, denoted γ(G) (γi(G)). The following result is well known.We thank the referees for pointing out an error in the original version of the paper which led to substantial improvement in the main result of this note. [Copyright &y& Elsevier]

In this paper we present an efficient Variable Neighbourhood Search for the k -labelled spanning forest (kLSF) problem, an NP-hard graph problem related to the minimum labelling spanning tree problem, and with strong implications in multimodal transportation networks. Given an undirected input graph whose edges are labelled, and an integer positive value k ¯ , the aim is to find a spanning forest of the input graph having the minimum number of connected components and the upper bound k ¯ on the number of labels to use. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents two extensions for DGVNS (Decomposition Guided VNS) method, that exploit both the graph of clusters and separators between these clusters, to efficiently guide the exploration of large neighborhoods in VNS. Experiments performed on challenging instances of the tagSNP selection problem show the appropriateness and the efficiency of our approach. [Copyright &y& Elsevier]

Abstract: Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some metaheuristics have been proposed and analyzed. A hybrid local search method is proposed in this paper. It is obtained by combining Variable Neighbourhood Search with Simulated Annealing. Computational experiments show that the proposed hybrid heuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time. [Copyright &y& Elsevier]

Abstract: The Cutwidth Minimization Problem, also known as the Minimum Cut Linear Arrangement consists of finding an arrangement of the vertices of a graph on a line, in such a way that the maximum number of edges between each pair of consecutive vertices is minimized. This problem has practical applications in VLSI Design, Network Migration and Graph Drawing, among others. In this paper we propose several heuristics based on the Variable Neighbourhood Search methodology to tackle the problem and we compare them with other state-of-the-art methods. [Copyright &y& Elsevier]

Abstract: In this paper, we improve the existing bounds [Calamoneri, T. and B. Sinaimeri, -Labeling of Oriented Planar Graphs (Extended Abstract), in: Proc. 12th Italian Conference on Theoretical Computer Science, (2010)] for 2-dipath and oriented span for the class of planar graphs with girth 5, 11, 16, cactus, wheels and leaf independent Halin graphs. Some of these bounds are tight. [Copyright &y& Elsevier]

Abstract: We consider the Minimum Rainbow Subgraph problem (MRS): Given a graph G, whose edges are coloured with p colours. Find a subgraph of minimum order and with p edges such that each colour occurs exactly once. This problem is APX-hard. In this paper we will show that the Greedy algorithm for the MRS problem has an approximation ratio of for graphs with maximum degree Δ. If the average degree d of a minimum rainbow subgraph is known, then the approximation ratio is . [Copyright &y& Elsevier]

Abstract: The work deals with a generalization of Erdős – Lovász problem concerning colorings of non-uniform hypergraphs. Let be a hypergraph and let for some . Erdős and Lovász asked about the value equal to the minimum possible value of where H is 3-chromatic hypergraph with minimum edge-cardinality n. In our paper we study similar problem in the class of hypergraphs with large girth. [Copyright &y& Elsevier]

Abstract: Let be a finite, simple, indirected and either connected or disconnected. A antimagic total labeling of a graph with p vertices and q edges is a bijection such that all vertex weights are pairwise distinct, where a vertex weight is the sum of the label of that vertex and labels of all edges incident with the vertex. A graph is antimagic total if it has an antimagic total labeling. An antimagic total labeling l of a graph is called super (resp. repus) if (resp. ). A graph is super (resp. repus) antimagic total if it has a super (resp. repus) antimagic total labeling. In this paper we prove that all graphs have antimagic total labelings. We also prove that all graphs have super antimagic total labelings and repus antimagic total labelings. Furthermore, we show that some graphs have super -antimagic total labelings and repus -antimagic total labelings, that is, labelings that use the p smallest labels (resp. p largest labels) on vertices and, moreover, the vertex weights form arithmetic progression. [Copyright &y& Elsevier]

Abstract: The independence number of a graph G, denoted by , is the cardinality of an independent set of maximum size in G, while is the size of a maximum matching in G, i.e., its matching number. G is a König–Egerváry graph if its order equals . In this paper we give a new characterization of König–Egerváry graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a König–Egerváry graph. [Copyright &y& Elsevier]

Abstract: This paper provides tight lower bounds on the maximum genus of a regular graph in terms of its cycle rank. The main tool is a relatively simple theorem that relates lower bounds with the existence (or non-existence) of induced subgraphs with odd cycle rank that are separated from the rest of the graph by cuts of size at most three. Lower bounds on the maximum genus are obtained by bounding from below the size of these odd subgraphs. As a special case, upper-embeddability of a class of graphs is caused by an absence of such subgraphs. A well-known theorem stating that every 4-edge-connected graph is upper-embeddable is a straightforward corollary of the employed method. [Copyright &y& Elsevier]

Abstract: Grünbaum [B. Grünbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970) 1131–1201] and independently Nash-Williams [C.St.J.A. Nash-Williams, Unexplored and semi-explored territories in graph theory, in “New directions in the theory of graphs” 149–186, Academic Press, New York, 1973] conjectured that every 4-connected graphs on the torus has a hamilton cycle. In this paper, we show that the conjecture is true for triangulations of the torus. [Copyright &y& Elsevier]

Abstract: Let F be a graph and k be a positive integer. With a graph G, we associate the quantity , the number of k-colorings of the edge set of G with no monochromatic copy of F. Consider the function given by , the maximum of over all graphs G on n vertices. In this paper we study the asymptotic behavior of and describe the extremal graphs for the case in which F is a matching, a short path or a star. [Copyright &y& Elsevier]

Abstract: A strong edge colouring of a graph G is a proper edge colouring such that every path of length 3 uses three colours. In this paper, we give some upper bounds for the minimum number of colours in a strong edge colouring of subcubic graphs as a function of the maximum average degree. We also prove the NP-completeness of the strong edge k-colouring problem for some restricted classes of subcubic planar graphs when . [Copyright &y& Elsevier]

Abstract: It has been observed that information spreads extremely fast in social networks. We model social networks with the preferential attachment model of Barabási and Albert (Science 1999) and information spreading with the random phone call model of Karp et al. (FOCS 2000). In a recent paper (STOC 2011), we prove the following two results. (i) The random phone call model delivers a message to all nodes of graphs in the preferential attachment model within rounds with high probability. The best known bound so far was . (ii) If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one , which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding doublecontacts reduces the run-time to a smaller order of magnitude. [Copyright &y& Elsevier]

Abstract: The minmax degree of a graph G, denoted , is the largest integer m such that every edge of G is incident with a vertex with degree at least m. The tight bounds are known for the minmax degree of planar graphs with minimum degree at least 2 and girth g for every g, unless when or . For these last values of g, we can find for any integer k a graph with . We define the 2-stackability of a graph G, denoted , as the maximum number of vertices with degree 2 that all are adjacent to the same pair of distinct vertices in G. In the complete version of the paper, we prove that, for a planar graph G with minimum degree at least 2, ; moreover, if G does not contain triangles. We also show that these bounds are tight. The maximum average degree of a graph G is . We prove that, for every and , every graph G with and has . We also show that these bound is the lowest possible. Borodin et al. [Borodin, O. V., A. V. Kostochka, N. N. Sheikh and G. Yu, M-degrees of quadrangle-free planar graph, J. Graph Theory 60 (2009), pp. 80–85] showed that if G is a planar graph with minimum degree at least 2 and without 4-cycles. Moreover, if G has neither 5-cycles, Borodin et al. [5] proved that . We prove that a planar graph G has if G has minimum degree at least 2, no 4-cycles, neither 5-cycles adjacent to a triangle incident to a vertex of degree 2. We give some other results about planar graphs with minimum degree at least 2 and without 4-cycles and intersecting triangles, with other restrictions on the cycles. These results imply results for edge-partitions of graphs and game coloring number. [Copyright &y& Elsevier]

Abstract: RNA (Ribonucleic acid) is an important molecule in the cell, which participates in a lot of basic biological functions. Hairpins and cloverleaves are two important structures in RNA secondary structures. In this paper, we use generating functions to enumerate RNA hairpins and Cloverleaves. We also point out incorrect results in literature. [Copyright &y& Elsevier]

Abstract: Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, , where is the connected domination number of G. Bounds of the form , for many special graph classes follow as easy corollaries from this result. We also show that every bridge-less chordal graph G has . An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree . This solves an open problem from Schiermeyer, 2009 [Schiermeyer, I. (2009). Rainbow connection in graphs with minimum degree three. In Fiala, J., Kratochvl, J., and Miller, M., editors, Combinatorial Algorithms, volume 5874 of Lecture Notes in Computer Science, pages 432–437. Springer Berlin / Heidelberg.], improving the previously best known bound of from Krivelevich and Yuster, 2010 [Krivelevich, M. and Yuster, R. (2010). The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3):185–191.]. Moreover, this bound is seen to be tight up to additive factors by a construction mentioned in Caro et. al., 2008 [Caro, Y., Lev, A., Roditty, Y., Tuza, Z., and Yuster, R. (2008). On rainbow connection. The electronic journal of combinatorics, 15(R57):1]. [Copyright &y& Elsevier]

Abstract: Edge-distance-regularity is a concept recently introduced by the authors which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edge-distance-regular when it is distance-regular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distance-regular graphs is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, it is shown that every nonbipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph. [Copyright &y& Elsevier]

Abstract: The notion of permutation capacities is motivated by and shows similarities with the Shannon capacity of graphs and its generalization to directed graphs called Sperner capacity. We show that families of oriented paths have a different behaviour with respect to these capacities than Shannon and Sperner capacities and their generalization to graph families do. The talk is based on the paper [Brightwell, G., G. Cohen, E. Fachini, M. Fairthorne, J. Körner, G. Simonyi, and Á. Tóth, Permutation capacities of families of oriented infinite paths, SIAM J. Discrete Math. 24 (2010), 441–456]. [Copyright &y& Elsevier]

Abstract: In 2010 Moreira and three of the current authors introduced a notion of property testing for permutations based on a distance that measures the randomness of a permutation. They proved that every hereditary permutation property is testable in this sense, or weakly testable in their terminology. In this paper, we show that hereditary permutation properties are testable in a stronger sense, namely when testability is defined by means of the usual -distance for permutations. This is the permutation analogue of the well-known Alon-Shapira result on the testability of hereditary graph properties. [Copyright &y& Elsevier]

Abstract: In the Boolean lattice the BLYM inequality holds with equality if and only if the Sperner family consists of one complete level of subsets. In this paper we extend this strict BLYM-property to a subclass of normal posets. On the basis of this result we prove a strict two-part Sperner theorem of the direct product of any two posets from the same subclass. [Copyright &y& Elsevier]

Abstract: The dichromatic polynomial can be characterized as the most general C-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion and edge contraction. Similarly, the universal edge elimination polynomial introduced in [Ilya Averbouch, Benny Godlin, and Johann A. Makowsky. An extension of the bivariate chromatic polynomial. Eur. J. Comb, 31(1):1–17, 2010] can be characterized as the most general EE-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion, edge contraction and edge extraction. In this paper we examine substitution instances of and show that among these the dichromatic polynomial plays a distinctive rôle. [Copyright &y& Elsevier]

Abstract: A d-dimensional polycube is a -face-connected set of cubes in d dimensions. Fixed polycubes are considered distinct if they differ in shape or orientation. The cube-adjacency graph of a tree polycube is a tree. In this paper we investigate the asymptotic growth rate of d-dimensional tree polycubes, and estimate it at . [Copyright &y& Elsevier]

Abstract: Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs. [Copyright &y& Elsevier]

Abstract: In few years, min-cut/max-flow approach has become a leading method for solving a wide range of problems in computer vision. However, min-cut/max-flow approaches involve the construction of huge graphs which sometimes do not fit in memory. Currently, most of the max-flow algorithms are impracticable to solve such large scale problems. In this paper, we introduce a new strategy for reducing exactly graphs in the image segmentation context. During the creation of the graph, we test if the node is really useful to the max-flow computation. Numerical experiments validate the relevance of this technique to segment large scale images. [Copyright &y& Elsevier]

Abstract: Given a simple and finite connected graph G, the distance is the length of the shortest -path in G. Cicerone and Di Stefano [Graphs with bounded induced distance, Discrete Applied Mathematics 108 (2001), pp. 3–21] introduced and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. In this paper we make a step forward in the study of such graphs by providing characterizations for k-distance-hereditary graphs, , in terms of both forbidden subgraphs and cycle-chord conditions. Such results lead to a polynomial-time recognition algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of -tidy graphs and ()-graphs, for every fixed q. These classes include cographs, -sparse and -lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of ()-graphs. All these coloring problems are known to be NP-hard for general graphs. [Copyright &y& Elsevier]

Abstract: The longest path problem asks for a path with the largest number of vertices in a given graph. The first polynomial time algorithm (with running time ) has been recently developed for interval graphs. Even though interval and circular-arc graphs look superficially similar, they differ substantially, as circular-arc graphs are not perfect. In this paper, we prove that for every path P of a circular-arc graph G, we can appropriately “cut” the circle, such that the obtained (not induced) interval subgraph of G admits a path on the same vertices as P. This non-trivial result is of independent interest, as it suggests a generic reduction of a number of path problems on circular-arc graphs to the case of interval graphs with a multiplicative linear time overhead of . As an application of this reduction, we present the first polynomial algorithm for the longest path problem on circular-arc graphs, which turns out to have the same running time with the one on interval graphs, as we manage to get rid of the linear overhead of the reduction. This algorithm computes in the same time an n-approximation of the number of different vertex sets that provide a longest path; in the case where G is an interval graph, we compute the exact number. Moreover, our algorithm can be directly extended with the same running time to the case where every vertex has an arbitrary positive weight. [Copyright &y& Elsevier]

Abstract: The idea of “Lemke pivoting in a family of oiks (Euler complexes)” generalizes, and abstracts to pure combinatorics, the Lemke-Howson exchange algorithm for finding a Nash equilibrium in bimatrix games, as well as the classical algorithm for finding the properly colored room in Sperner''s Lemma. Given a “room-partitioning”, this algorithm finds another (distinct) room-partitioning by traversing the exchange graph. In this paper we show that each family of k oiks can be reduced to a pair of oiks (one of which, , is a Sperner oik) such that the exchange graphs for and are isomorphic. Numerous applications of Sperner''s Lemma in combinatorial topology are well known. [Copyright &y& Elsevier]

Abstract: In this paper we study the lift-and-project polyhedral operators defined by Lovász and Schrijver [L. Lovász, A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optimization 1, (1991), pp. 166–190] and by Balas, Ceria and Cornuéjols [3] on the clique relaxation of the stable set polytope of webs. We prove they have the same perfomance when starting from the clique relaxation of the family of webs . Considering the lift-and-project strength of facets for the stable set polytope on webs defined in [S. Bianchi, M. Escalante, M.S. Montelar, Strength of facets for the set covering and set packing polyhedra on circulant matrices, Electronic Notes in Discrete Mathematics 35, (2009), pp. 109-114], we obtain that the facets of maximum strength for the family are also the facets of maximum strength according to Goemans'' measure [M. Goemans, Worst-case Comparison of Valid Inequalities for the TSP, Mathematical Programming, Fifth Integer Programming and Combinatorial Optimization Conference, LNCS 1084, Vancouver, Canada, (1996), pp. 415–429]. This last result is obtained by means of the imperfection index and imperfection ratio defined in [N. Aguilera, G. Nasini, M. Escalante, A generalization of the perfect graph theorem under the disjunctive index, Mathematics of Operations Research Vol. 27, No 3, (2002) pp. 460–469] and [S. Gerke, C. McDiarmid, Graph imperfection, Journal of Combinatorial Theory Series B 83, (2001), pp. 58–78]. [Copyright &y& Elsevier]

Abstract: In this paper we give an explicit description of the stable set polytope of a claw-free graph obtained by repeated applications of the strip composition of fuzzy linear interval strips, fuzzy XX-strips, and fuzzy antihat strips. Using a decomposition theorem of Chudnovsky and Seymour, this allows us to describe the stable set polytope of all facet defining claw-free graphs with stability number greater than 3. [ABSTRACT FROM AUTHOR]

Abstract: Given an undirected graph and two specified nonadjacent nodes a and b of V, a cut separator is a subset such that and a and b belong to different connected components of the graph induced by . Given a nonnegative cost vector , cut separator of minimum cost. This new problem is closely related to the vertex separator problem. In this paper, we give a polynomial time algorithm for this problem. We also present four equivalent linear formulations, and we show their tightness. Using these results we obtain an explicit short polyhedral description of the dominant of the cut separator polytope. [ABSTRACT FROM AUTHOR]

Abstract: An efficient use of dynamic programming requires a substantial reduction of the number of labels. We propose in this paper an efficient way of reducing the number of labels saved and dominance computing time. Our approach is validated by experiments on shortest path problem with time windows instances. [ABSTRACT FROM AUTHOR]

Abstract: The sum coloring problem has many applications in scheduling. It is a variant of the vertex coloring problem where the objective is to minimize the sum of colors used in coloring the vertices. In this paper, we use tabu search to solve the sum coloring problem. Experiments are performed on instances extracted from the second DIMACS challenge. Results show significative improvements on some chromatic sum bounds. [ABSTRACT FROM AUTHOR]

Abstract: Minimum Linear Arrangement is a classical basic combinatorial optimization problem from the 1960s, which turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best known solution value often has one more digit than the best known lower bound value. In this paper, we propose a linear-programming based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best known solutions are indeed not far from optimal for most of the benchmark instances. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the generalization of Zinder-Roper algorithm for maximum lateness problem to the case of dedicated processors systems with constant delays. One of remarkable feature of this algorithm is that it is based on iterated list scheduling, without any other computation. The performance of the extended algorithm is evaluated through worst-case analysis. If all tasks have the same type and no delay is considered, then the upper bound obtained coincides with the upper bound for Zinder-Roper algorithm on identical processors, which is the best known for maximum lateness problem. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate heuristics for approximate graph matching, in particular its formulation as a Maximum Common Edge Subgraph problem. Our experiments suggest that a small percentage of accurate node matches is sufficient to get near optimal solutions using a simple hill-climbing. The real challenge could then be to somehow drag the search in this zone. For this purpose, we discuss the use of similarity measures. We present and assess the performance of two similarity measures. Very good results were obtained on labeled graphs. [ABSTRACT FROM AUTHOR]