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]

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]

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]

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: 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 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: 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: 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: 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 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: A defensive alliance in a graph is a set of vertices satisfying the condition that, for each , at least one half of its closed neighbors are in . A defensive alliance is called a critical defensive alliance if any vertex is removed from , then the resulting vertex set is not a defensive alliance any more. An alliance is called global if every vertex in is adjacent to at least one member of the alliance . In this paper, we shall propose a way for finding a critical global defensive alliance of star graphs. After counting the number of vertices in the critical global defensive alliance, we can derive an upper bound to the size of the minimum global defensive alliances in star graphs. [Copyright &y& Elsevier]

Abstract: The reinforcement number of a graph is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of . In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs. [Copyright &y& Elsevier]

Abstract: Assume we have a set of colors and we assign an arbitrary subset of these colors to each vertex of a graph . If we require that each vertex to which an empty set is assigned has in its neighborhood all colors, then this assignment is called the -rainbow dominating function of a graph . The corresponding invariant , which is the minimum sum of numbers of assigned colors over all vertices of , is called the -rainbow domination number of . Brešar and S˘umenjak [B. Brešar, T.K. S˘umenjak On the 2-rainbow domination in graphs, Discrete Applied Mathematics, 155 (2007) 2394–2400] showed that , where for and for . And they raised the question: Is for all ? In this paper, we put forward the answer to the question. More over, we show that , where for and for . [Copyright &y& Elsevier]

Abstract: Let be a finite and simple graph with vertex set , and let be a two-valued function. If for each , where is the closed neighborhood of , then is a signed dominating function on . A set of signed dominating functions on with the property that for each , is called a signed dominating family (of functions) on . The maximum number of functions in a signed dominating family on is the signed domatic number on . In this paper, we investigate the signed domatic number of some circulant graphs and of the torus . [Copyright &y& Elsevier]

Abstract: The fractional weak discrepancy of a poset was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227–2235] as the minimum nonnegative for which there exists a function satisfying (i) if then and (ii) if then . In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51–63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291–302] on the range of the function for semiorders (interval orders with no induced ) to interval orders with no , where . In particular, we prove that the range for such posets is the set of rationals that can be written as , where . If and has an optimal forcing cycle with and , then . Moreover when , for each satisfying there is an interval order having such an optimal forcing cycle and containing no. [Copyright &y& Elsevier]

Abstract: The tenacity of a graph , , is defined by , where the minimum is taken over all vertex cutsets of , be the number of components of and be the number of vertices in the largest component of the graph induced by . A -tree of a connected graph is a spanning tree with maximum degree at most . In this paper we show that if , for any subset of , with , then has a -tree. [Copyright &y& Elsevier]

Abstract: In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter . Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of . It also allows us to apply results on local search algorithms on graphs to obtain a approximation for the weighted MIS and approximation for the unweighted case. We improve the bound in the weighted case to using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of , significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of . [Copyright &y& Elsevier]

Abstract: Let denote the set of unicyclic graphs with a given diameter . In this paper, the unique unicyclic graph in with the maximum number of independent sets, is characterized. [Copyright &y& Elsevier]

Abstract: Given an acyclic digraph , the competition graph of is the graph with the same vertex set as where two distinct vertices and are adjacent in if and only if there is a vertex in such that and are arcs of . The competition number of a graph is the least number of isolated vertices that must be added to to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly holes, all of which are independent, is at most . This generalizes the result for given by Roberts, and the result for given by Cho and Kim. [Copyright &y& Elsevier]

Abstract: Let be a graph. A function defined on the vertices of is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function is minimal if there does not exist a signed total dominating function , , for which for every . The weight of a signed total dominating function is the sum of its function values over all vertices of . The upper signed total domination number of is the maximum weight of a minimal signed total dominating function on . In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs. [Copyright &y& Elsevier]

Abstract: Let denote the number of odd components of a graph G. The deficiency of G is defined as , and this equals the number of vertices unmatched by any maximum matching of G. A subset is called a Tutte set (or barrier set) of G if , and an extreme set if . Recently a graph operator, called the D-graph , was defined that has proven very useful in examining Tutte sets and extreme sets of graphs which contain a perfect matching. In this paper we give two natural and related generalizations of the D-graph operator to all simple graphs, both of which have analogues for many of the interesting and useful properties of the original. [Copyright &y& Elsevier]

Abstract: In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in [J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, SIAM J. Discrete Math. 11 (1998) 655–663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201–225; A.N. Trenk, On k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223–237]. The fractional weak discrepancy of a poset is the minimum nonnegative k for which there exists a function satisfying (1) if then and (2) if then . We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset. [Copyright &y& Elsevier]

Abstract: A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs. [Copyright &y& Elsevier]

Abstract: The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater''s problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree. [Copyright &y& Elsevier]

Abstract: We consider the problem of numerical representations of PQI interval orders. A preference structure on a finite set A with three relations standing for “strict preference”, “weak preference” and “indifference”, respectively, is defined as a PQI interval order iff there exists a representation of each element of A by an interval in such a way that, P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non-empty intersection (Q modelling the hesitation between P and I). Only recently, necessary and sufficient conditions for a PQI preference structure to be identified as a PQI interval order have been established. In this paper, we are interested in the problem of constructing a numerical representation of a PQI interval order and possibly a minimal one. We present two algorithms, the first one in aimed to determine a general numerical representation, and the second one, in , aimed to minimise such a representation. [Copyright &y& Elsevier]

Abstract: This paper deals with the graph isomorphism (GI) problem for two graph classes: chordal bipartite graphs and strongly chordal graphs. It is known that GI problem is GI complete even for some special graph classes including regular graphs, bipartite graphs, chordal graphs, comparability graphs, split graphs, and k-trees with unbounded k. On the other hand, the relative complexity of the GI problem for the above classes was unknown. We prove that deciding isomorphism of the classes are GI complete. [Copyright &y& Elsevier]