Search

In Vukicevic and Stevanovic (2013), Theorem 2 is erroneous when m = 3 k + 1 for some integer k . The correct one is given now. That is, P I ( G ) ≥ m 2 − 3 m + 2 when m = 3 k + 1 for some integer k , where G is a connected bicyclic graph with m edges.

A graph is perfect if the size of the maximum clique equals the chromatic number in every induced subgraph. Chvatal defined a subclass of perfect graphs known as perfectly-orderable graphs, which have the property that a special ordering on the vertices leads to a trivial algorithm to find an optimum coloring. He also identified a subclass of the perfectly-orderable graphs, which he called brittle graphs, characterized by the property that every nonempty induced subgraph contains a vertex x such that x is either not an endpoint of a P 4 or is not in the middle of a P 4 . The brittle graphs were studied in a recent paper of Hoang and Khouzam [J. Graph Theory 12 (1988) 391-404] where the authors gave alternate characterizations one of which leads to an O( n 3 m ) time recognition algorithm for brittle graphs, where n is the number of vertices and m is the number of edges. In contrast, no polynomial-time recognition algorithms are known for either perfect graphs or perfectly-orderable graphs. We point out that an O( n 2 m ) time recognition algorithm for brittle graphs can be derived from Chvatal's definition, and we present a more complicated O( m 2 ) time recognition algorithm.

Let $n, r, k$ be positive integers such that $3\leq k < n$ and $2\leq r \leq k-1$. Let $m(n, r, k)$ denote the maximum number of edges an $r$-uniform hypergraph on $n$ vertices can have under the condition that any collection of $i$ edges, span at least $i$ vertices for all $1 \leq i \leq k$. We are interested in the asymptotic nature of $m(n, r, k)$ for fixed $r$ and $k$ as $n \rightarrow \infty$. This problem is related to the forbidden hypergraph problem introduced by Brown, Erd\H{o}s, and S\'os and very recently discussed in the context of combinatorial batch codes. In this short paper we obtain the following results. {enumerate}[(i)] Using a result due to Erd\H{o}s we are able to show $m(n, k, r) = o(n^r)$ for $7\leq k$, and $3 \leq r \leq k-1-\lceil\log k \rceil$. This result is best possible with respect to the upper bound on $r$ as we subsequently show through explicit construction that for $6 \leq k$, and $k-\lceil \log k \rceil \leq r \leq k-1, m(n, r, k) = \Theta(n^r)$. This explicit construction improves on the non-constructive general lower bound obtained by Brown, Erd\H{o}s, and S\'os for the considered parameter values. For 2-uniform CBCs we obtain the following results. {enumerate} We provide exact value of $m(n, 2, 5)$ for $n \geq 5$. Using a result of Lazebnik,et al. regarding maximum size of graphs with large girth, we improve the existing lower bound on $m(n, 2, k)$ ($\Omega(n^{\frac{k+1}{k-1}})$) for all $k \geq 8$ and infinitely many values of $n$. We show $m(n, 2, k) = O(n^{1+\frac{1}{\lfloor\frac{k}{4}\rfloor}})$ by using a result due to Bondy and Simonovits, and also show $m(n, 2, k) = \Theta(n^{3/2})$ for $k = 6, 7, 8$ by using a result of K\"{o}vari, S\'os, and Tur\'{a}n., Comment: 9 pages

The classical Dirac theorem asserts that every graph G on n ≥ 3 vertices with minimum degree δ ( G ) ≥ ⌈ n ∕ 2 ⌉ is Hamiltonian. The lower bound of ⌈ n ∕ 2 ⌉ on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where δ ( G ) ≥ ⌊ n ∕ 2 ⌋ by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph G with δ ( G ) ≥ ⌊ n ∕ 2 ⌋ , or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when δ ( G ) ≥ ⌊ n ∕ 2 ⌋ and is promising for extending the results of this paper to the cases with smaller degree bounds.

And/or graphs are well-known data structures with several applications in many fields of computer science, such as Artificial Intelligence, Distributed Systems, Software Engineering, and Operations Research. An and/or graph is an acyclic digraph G containing a single source vertex s , where every vertex v ∈ V ( G ) has a label f ( v ) ∈ { and,or }. In an and/or graph, (weighted) edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. A solution subgraph H of an and/or graph G is a subdigraph of G containing its source vertex and such that if an and -vertex (resp. or -vertex) is included in H then all (resp. one) of its out-edges must also be included in H . In general, solution subgraphs represent feasible solutions of problems modeled by and/or graphs. The optimization problem associated with an and/or graph G consists of finding a minimum weight solution subgraph H of G , where the weight of a solution subgraph is the sum of the weights of its edges. Because of its wide applicability, in this work we develop a multivariate investigation of this optimization problem. In a previous paper (Souza et al., 2013) we have analyzed the complexity of such a problem under various aspects, including parameterized versions of it. However, the main open question has remained open: Is the problem of finding a solution subgraph of weight at most k (where k is the parameter) in FPT? In this paper we answer negatively to this question, proving the W[1]-hardness of the problem, and its W[P]-completeness when zero-weight edges are allowed. We also show that the problem is fixed-parameter tractable when parameterized by the tree-width, but it is W[SAT]-hard with respect to the clique-width and k as aggregated parameters. In addition, we show that when the out-edges of each or -vertex have all the same weight (a condition very common in practice), the problem becomes fixed-parameter tractable by the clique-width. Finally, using a framework developed by Bodlaender et al. (2009) and Fortnow and Santhanam (2011), based upon the notion of compositionality, we show that the tractable cases do not admit a polynomial kernel unless NP ⊆ coNP∕poly , even restricted to instances without or -vertices with out-degree greater than two.

A set D ⊆ V is called a k -tuple dominating set of a graph G = ( V , E ) if | N G [ v ] ∩ D | ≥ k for all v ∈ V , where N G [ v ] denotes the closed neighborhood of v . A set D ⊆ V is called a liar’s dominating set of a graph G = ( V , E ) if (i) | N G [ v ] ∩ D | ≥ 2 for all v ∈ V and (ii) for every pair of distinct vertices u , v ∈ V , | ( N G [ u ] ∪ N G [ v ] ) ∩ D | ≥ 3 . Given a graph G , the decision versions of k - Tuple Domination Problem and the Liar’s Domination Problem are to check whether there exist a k -tuple dominating set and a liar’s dominating set of G of a given cardinality, respectively. These two problems are known to be NP -complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k - Tuple Domination Problem and the Liar’s Domination Problem are W[2] -hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems.

Given a set L of graphs, a graph G is L -free if G does not contain any graph in L as an induced subgraph. There has been keen interest in colouring graphs whose forbidden list L contains graphs with four vertices. A recent paper of Lozin and Malyshev (in press) discusses the state of the art on this problem, identifying three outstanding classes: L = ( 4 K 1 , claw ) , L = ( 4 K 1 , claw, co-diamond ) , and L = ( 4 K 1 , C 4 ) . In this paper we investigate the class of ( 4 K 1 , C 4 , C 5 )-free graphs and show that if G is a ( 4 K 1 , C 4 , C 5 )-free graph, then G either has bounded clique width or is perfect.

A circulant graph C n ( a 1 , … , a k ) is a graph with n vertices { v 0 , … , v n − 1 } such that each vertex v i is adjacent to vertices v ( i + a j ) m o d n , for j = 1 , … , k . In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O ( k 3 log 2 n + n ) algorithm for a subclass of 3-chromatic C n ( a 1 , … , a k ) ’s with k ≥ 2 , which are characterized in the paper.

The present paper shows an extension of the theory of principal partitions for submodular functions to that for bisubmodular functions. We examine the structure of the collection of all solutions of a parametric minimization problem described by a bisubmodular function and two vectors. The bisubmodular function to be minimized for each parameter is the sum of the bisubmodular function and a parameterized box-bisubmodular function given in terms of the two vectors. We show that the collection of all the minimizers for all parameters forms a signed ring family and it thus induces a signed poset on a signed partition of the underlying set. We further examine the structure of the signed ring family and reveal the decomposition structure depending on critical values of the parameter. Moreover, we discuss the relation between the results of this paper on bisubmodular functions and the theory of principal partitions developed for submodular functions.

Wireless sensor networks are commonly used to monitor various environmental conditions. Possible geometries for the region covered by a sensor include disks, wedges, and rays, among others, depending on the function of the sensor. In this paper we consider a network consisting of ray sensors deployed to detect intruders traversing a path, not necessarily straight, from a source to a destination . The coverage of the network with respect to and can be modeled by a tripartite graph, the barrier graph of the network. While all barrier graphs are tripartite, the converse is not true (for instance, C5 is not a barrier graph).The main result of this paper is a rigidity theorem on the structure of barrier graphs that results from constraints imposed by the geometry of the network. This allows us to show that almost all bipartite graphs are not barrier graphs, despite the fact that various classes of bipartite graphs, including trees, cycles of even length, and Km,n are barrier graphs. Furthermore, vertex cover of a barrier graph corresponds to a set of sensors whose removal allows a clear path from to . While all bipartite graphs with small vertex covers are barrier graphs (a fact we prove for sizes less than 4), the rigidity property also implies that graphs with vertex covers bigger than a certain constant are not barrier graphs.

A proper t -edge-coloring of a graph G is a mapping α : E ( G ) → { 1 , … , t } such that all colors are used, and α ( e ) ≠ α ( e ′ ) for every pair of adjacent edges e , e ′ ∈ E ( G ) . If α is a proper edge-coloring of a graph G and v ∈ V ( G ) , then the spectrum of a vertex v , denoted by S ( v , α ) , is the set of all colors appearing on edges incident to v . The deficiency of α at vertex v ∈ V ( G ) , denoted by d e f ( v , α ) , is the minimum number of integers which must be added to S ( v , α ) to form an interval, and the deficiency d e f ( G , α ) of a proper edge-coloring α of G is defined as the sum ∑ v ∈ V ( G ) d e f ( v , α ) . The deficiency of a graph G , denoted by d e f ( G ) , is defined as follows: d e f ( G ) = min α d e f ( G , α ) , where minimum is taken over all possible proper edge-colorings of G . For a graph G , the smallest and the largest values of t for which it has a proper t -edge-coloring α with deficiency d e f ( G , α ) = d e f ( G ) are denoted by w d e f ( G ) and W d e f ( G ) , respectively. In this paper, we obtain some bounds on w d e f ( G ) and W d e f ( G ) . In particular, we show that for any l ∈ N , there exists a graph G such that d e f ( G ) > 0 and W d e f ( G ) − w d e f ( G ) ≥ l . It is known that for the complete graph K 2 n + 1 , d e f ( K 2 n + 1 ) = n ( n ∈ N ). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Haluszczak posed the following conjecture on the deficiency of near-complete graphs: if n ∈ N , then d e f ( K 2 n + 1 − e ) = n − 1 . In this paper, we confirm this conjecture.

For a connected graph G=(V(G),E(G)) and two disjoint subsets of V(G)A={1,,k} and B={1,,k}, a paired (many-to-many) k-disjoint path cover of G joining A and B is a vertex-disjoint path cover {P1,,Pk} such that Pi is a path from i to i for 1ik. In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 2-disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O(|V(G)|+|E(G)|)-time algorithm that actually finds such a paired 2-disjoint path cover. In particular, we show that, in order to build a desired disjoint path cover, it is sufficient to consider only the edges of a carefully selected spanning tree of the graph and at most one additional edge not in the tree, which allows an efficient linear-time algorithm.

The problems of counting independent sets, maximal independent sets, and independent perfect dominating sets are #P-complete for bipartite graphs, but can be solved in polynomial time for convex bipartite graphs, which are a subclass of bipartite graphs This paper studies these problems for tree convex bipartite graphs, which are a class of graphs between bipartite graphs and convex bipartite graphs. A bipartite graph G with bipartition (XY) is called tree convex, if a tree T defined on X exists, such that for every vertex y in Y, the neighbors of y form a subtree of T If the associated tree T is simply a path, then G is just a convex bipartite graph. This paper first proves that the problems of counting independent sets, maximal independent sets, and independent perfect dominating sets remain #P-complete for tree convex bipartite graphs even when the associated tree T is only a comb or a star. This paper then presents polynomial-time algorithms to solve these problems for tree convex bipartite graphs when the associated tree T is restricted to a triad, which consists of three paths with one common endpoint.

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.

It has been known since 1996 (work of Cai et al.) that the sequence of Hamming weights { w t ( f n ( x 1 , ź , x n ) ) } , where f n is a symmetric Boolean function of degree d in n variables, satisfies a linear recurrence with integer coefficients. In 2011, Castro and Medina used this result to show that a 2008 conjecture of Cusick, Li and Stźnicź about when an elementary symmetric Boolean function can be balanced is true for all sufficiently large n . Quite a few papers have been written about this conjecture, but it is still not completely settled. Recently, Guo, Gao and Zhao proved that the conjecture is equivalent to the statement that all balanced elementary symmetric Boolean functions are trivially balanced. This motivates the further study of the weights of symmetric Boolean functions f n . In this paper we prove various new results on the trivially balanced functions. We also determine a period (sometimes the minimal one) for the sequence of weights w t ( f n ) modulo any odd prime p , where f n is any symmetric function, and we prove some related results about the balanced symmetric functions.

For any two vertices x and y of a graph G , let S { x , y } denote the set of vertices z such that either x lies on a y - z geodesic or y lies on an x - z geodesic. For a function g defined on V ( G ) and U ź V ( G ) , let g ( U ) = ź x ź U g ( x ) . A function g : V ( G ) ź 0 , 1 is a strong resolving function of G if g ( S { x , y } ) ź 1 , for every pair of distinct vertices x , y of G . The fractional strong metric dimension, s d i m f ( G ) , of a graph G is min { g ( V ( G ) ) : g źisźaźstrongźresolvingźfunctionźofź G } . This paper furthers the study of fractional strong metric dimension initiated in COCOA 2013 (Lecture Notes in Comput. Sci.). First, we clarify or correct the proofs to two characterization theorems contained in two papers on fractional (strong) metric dimension. Next, results on fractional strong metric dimension analogous to the work of Feng, Lv, and Wang on fractional metric dimension are offered. We provide new upper and lower bounds on s d i m f ( G ) , partly in analogy with the work done by Feng et al. and partly by exploiting the particular nature of the strong metric dimension. Finally, motivated by the work of Arumugam, Mathew, and Shen, we describe a class of graphs G for which s d i m f ( G ) = | V ( G ) | 2 .

In this paper we study the Wiener index (i.e.,źthe total distance or the transmission number) of not necessarily strongly connected digraphs. In order to do so, if in a digraph there is no directed path from a vertex a to a vertex b , we follow the convention that d ( a , b ) = 0 , which was independently introduced in several studies of directed networks. By extending the results of Plesnik and Moon we characterize tournaments with the maximal and the second maximal Wiener index. We also study oriented Theta-graphs and, as a consequence, we obtain that an orientation of a given graph which yields the maximum Wiener index is not necessarily strongly connected. In particular, we characterize orientations of Theta-graphs ź a , b , 0 and ź a , b , 1 which result in the maximum Wiener index. In addition, orientations with the maximum Wiener index among strongly connected orientations of ź a , b , c are characterized. We conclude the paper with several open problems.

In this paper, we continue the study of the recently introduced total domination game in graphs. A vertex u in a graph G totally dominates a vertex? v if u is adjacent to v in G . A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S . The total domination game played on G consists of two players, named Dominator and Staller, who alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, γ tg ( G ) , of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, γ tg ' ( G ) , of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper we determine γ tg ( G ) and γ tg ' ( G ) when G is a cycle or a path. In particular, we show that for a cycle C n on n ? 3 vertices, γ tg ( C n ) = ? 2 n + 1 3 ? - 1 when n ? 4 ( mod 6 ) and γ tg ( C n ) = ? 2 n + 1 3 ? otherwise. Further, γ tg ' ( C n ) = ? 2 n 3 ? - 1 when n ? 2 ( mod 6 ) and γ tg ' ( C n ) = ? 2 n 3 ? otherwise. For a path P n on n ? 3 vertices, we show that γ tg ' ( P n ) = ? 2 n 3 ? . Further, γ tg ( P n ) = ? 2 n 3 ? when n ? 5 ( mod 6 ) and ? 2 n 3 ? otherwise.

Let K t denote the complete graph with t vertices, and let K 1 , m (a star with m edges) denote the complete bipartite graph with partite sets of sizes 1 and m . A graph G of order n is weakly F -saturated if G contains no copy of F , and there is an ordering of the edges in E ( K n ? G ) so that if they are added one at a time, then each edge added creates a new copy of F . In this paper, the weak saturation number of multiple copies of K t - K 1 , m is determined for positive integers t and m ( 1 ? m < t - 1 ) . This completely answers the question 3 in paper Faudree et?al. (2013), partially answers the question 4 in paper Faudree et?al. (2013) and the question 1 in Faudree and Gould (2014).

The first-order edge-tenacity T 1 ( G ) of a graph G is defined as T 1 ( G ) = m i n { | X | + ? ( G - X ) ω ( G - X ) - 1 } where the minimum is taken over every edge-cutset X that separates G into ω ( G - X ) components, and by ? ( G - X ) we denote the order (the number of edges) of a largest component of G - X .The objective of this paper is to study this concept of edge-tenacity and determining this quantity for some special classes of graphs. We calculate the first-order edge-tenacity of a complete n -partite graph. We shall obtain the first-order edge-tenacity of maximal planar graphs, maximal outerplanar graphs, and k -trees. Let G be a graph of order p and size q , we shall call the least integer r , 1 ? r ? p - 1 , with T r ( G ) = q p - r the balancity of G and denote it by b ( G ) . Note that the balancity exists since T r ( G ) = q p - r if r = p - 1 . In general, it is difficult to determine the balancity of a graph. In this paper, we shall first determine the balancity of a special class of graphs and use this to find an upper bound for the balancity of an arbitrary graph.

Broere and Hattingh proved that the Kronecker product of two circulants whose orders are co-prime is a circulant itself. This paper builds on this result to construct a family of efficient three-colorable, six-regular circulants representable as the Kronecker product of a Mobius ladder and an odd cycle. The order of each graph is equal to 4 d 2 - 2 d - 2 where d denotes the diameter and d ? 3 , 5 (mod 6). Additional results include (a) distance-wise vertex distribution of the circulant leading to its average distance that is about two-thirds of the diameter, (b) routing via shortest paths, and (c) an embedding of the circulant on a torus with a half twist. In terms of the order-diameter ratio and odd girth, the circulants in this paper surpass the well-known triple-loop networks having diameter d and order 3 d 2 + 3 d + 1 .

In the t -Latency-Bounded Target Set Selection ( t -LBTSS) problem, we are given a simple graph G = ( V , E ) , a certain latency bound t and a threshold function ? ( v ) = ? ? d ( v ) ? for every vertex v of G , where 0 < ? < 1 is a rational number and d ( v ) is the degree of v in V , the goal is to find a target set S with smallest cardinality such that all vertices in V are activated by S by a so called "diffusion process" within t rounds as follows: Initially, all vertices in the target set become activate. Then at each step i of the process, each vertex get activated if the number of active vertices in its neighbor after i - 1 exceeds its threshold.For general graphs, the t -LBTSS problem is not only NP-hard, it is also hard to be approximated by Chen's inapproachability results (Chen, 2009). In this paper, we are interested in finding an optimal target set for some special family of graphs. A simple, tight but nontrivial inequality was presented which gives the lower bound of the total sum of degrees in a feasible target set to t -LBTSS problem, in terms of the number of edges in the graph. Necessary and sufficient conditions for equality to hold have been established, based on which we are able to construct families of infinite number of graphs for which the optimal solution to t -LBTSS problem become obvious. In particular, we gave an exact formula for the optimal solution of a kind of toroidal mesh graphs, while it seems difficult to tell what the optimal solutions are for these graphs without using the equality given in the paper.

A graph $G=(V,E)$ is a \emph{word-representable graph} if there exists a word $W$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $W$ if and only if $(x,y)\in E$ for each $x\neq y$. In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a \emph{semi-transitive orientation} defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of $G$ is the minimum $k$ such that $G$ is a representable by a word, where each letter occurs $k$ times; such a $k$ exists for any word-representable graph. We show that the representation number of a word-representable graph on $n$ vertices is at most $2n$, while there exist graphs for which it is $n/2$., arXiv admin note: text overlap with arXiv:0810.0310

In 1965, Motzkin and Straus established a remarkable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turan's theorem using the connection. The connection of Lagrangians and Turan densities can be also used to prove the fundamental theorem of Erd?s-Stone-Simonovits on Turan densities of graphs. Very recently, the study of Turan densities of non-uniform hypergraphs has been motivated by extremal poset problems and suggested by Johnston and Lu. In this paper, we attempt to explore the applications of Lagrangian method in determining Turan densities of non-uniform hypergraphs. We first give a definition of the Lagrangian of a non-uniform hypergraph, then give an extension of the Motzkin-Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of the Erd?s-Stone-Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Our approach follows from the approach in Keevash's paper Keevash (2011).

While tools from structural graph theory such as tree- or path-width have proved to be highly successful in coping with computational intractability on undirected graphs, corresponding width measures for directed graphs have not yet fulfilled their promise for broad algorithmic applications on directed graphs. One reason for this is that in most existing digraph width measures the class of acyclic digraphs has small width which immediately implies hardness of problems such as computing directed dominating sets.Fernau and Meister (2014) introduce the concept of elimination width and a corresponding graph searching game which overcomes this problem with acyclic digraphs. In their paper, the focus was on structural characterizations of classes of digraphs of bounded elimination width.In this paper we study elimination width from an algorithmic and graph searching perspective. We analyse variations of the elimination width game and show that this leads to width measures on which the directed dominating set problem and some variants of it become tractable.

In this paper, we study a new graph invariant named reformulated reciprocal sum-degree distance ( R ¯ t ) , which is defined for a connected graph G as R ¯ t ( G ) = ∑ { u , v } ⊆ V G ( d G ( u ) + d G ( v ) ) 1 d G ( u , v ) + t , t ≥ 0 . On the one hand, this new graph invariant R ¯ t is a weight version of the t -Harary index, i.e., H t ( G ) = ∑ { u , v } ⊆ V G 1 d G ( u , v ) + t defined by Das et al. (2013). On the other hand, it is also the generalized version of reciprocal sum-degree distance of a connected graph, which is defined as R ( G ) = ∑ { u , v } ⊆ V G ( d G ( u ) + d G ( v ) ) 1 d G ( u , v ) ; see Alizadeh et al. (2013) and Hua and Zhang (2012). In this paper we introduce three edge-grafting transformations to study the mathematical properties of R ¯ t ( G ) . Using these nice mathematical properties, we characterize the extremal graphs among n -vertex trees with given graphic parameters, such as pendants, matching number, domination number, diameter, and vertex bipartition. Some sharp upper bounds on the reformulated reciprocal sum-degree distance of trees are determined.

We investigate the set of cycle lengths occurring in bipartite graphs with large minimum degree. A bipartite graph is weakly bipancyclic if it contains cycles of every even length between the length of a shortest and a longest cycle. In this paper, it is shown that if G = ( V 1 , V 2 , E ) is a bipartite graph with minimum degree at least n / 3 + 4 , where n = max { | V 1 | , | V 2 | } , then G is a weakly bipancyclic graph of girth 4. This improves a theorem of Tian and Zang (1989), which asserts that if G is a Hamilton bipartite graph on 2 n ( n ≥ 60 ) vertices with minimum degree greater than 2 n / 5 + 2 , then G is bipancyclic (i.e., G contains cycles of every even length between 4 and 2 n ). By combining the main result of our paper with a theorem of Jackson and Li (1994), we obtain that every 2-connected k -regular bipartite graph on at most 6 k − 38 vertices is bipancyclic.

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability, the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271-284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs.

This paper considers the relaxation procedure on a graph G with V ( G ) = { v 1 , v 2 , ? , v n } . Initially, a configuration X = ( x 1 , x 2 , ? , x n ) which is an n -tuple of real numbers having a positive sum is given. If there is a negative label x i , then the player can transform X into X ' = ( x 1 ' , x 2 ' , ? , x n ' ) , where x i ' = - x i , x j ' = x j + 2 d i x i for each v j adjacent to v i where v i has exactly d i neighbors, and x k ' = x k for all other k . Wegert and Reiher (Wegert and Reiher (2009)) proved the finiteness of the procedure and proposed the problem of determining graphs for which the final configurations and/or the numbers of steps are unique. In this paper, we give a complete solution to the problem.

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph $G=(V,E)$ and two "object types" $\mathrm{A}$ and $\mathrm{B}$ chosen from the alternatives above, we consider the following questions. \textbf{Packing problem:} can we find an object of type $\mathrm{A}$ and one of type $\mathrm{B}$ in the edge set $E$ of $G$, so that they are edge-disjoint? \textbf{Partitioning problem:} can we partition $E$ into an object of type $\mathrm{A}$ and one of type $\mathrm{B}$? \textbf{Covering problem:} can we cover $E$ with an object of type $\mathrm{A}$, and an object of type $\mathrm{B}$? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an $s$-$t$ path $P$ and an $s'$-$t'$ path $P'$ that are edge-disjoint. However, many others were not, for example can we find an $s$-$t$ path $P\subseteq E $ and a spanning tree $T\subseteq E$ that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense).

Homogeneous rotation symmetric (invariant under cyclic permutation of the variables) Boolean functions have been extensively studied in recent years due to their applications in cryptography. In this paper we give an explicit formula for the number of homogeneous rotation symmetric functions over the finite field GF(p^m) using Polya's enumeration theorem, which completely solves the open problem proposed by Yuan Li in 2008. This result simplifies the proof and the nonexplicit counting formula given by Shaojing Fu et al. over the field GF(p). This paper also gives an explicit count for n-variable balanced rotation symmetric Boolean functions with n=pq, where p and q are distinct primes. Previous work only gave an explicit count for the case where n is prime and lower bounds for the case where n is a prime power.

In this paper we deal with cover-incomparability graphs of posets. It is known that the class of cover-incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of s-subgraph which enables us to define forbidden s-subgraphs (i.e. graphs that cannot appear as s-subgraphs of any cover-incomparability graph). We show that the family of minimal forbidden s-subgraphs is infinite even for cover-incomparability unit-interval graphs. Using the notion of s-subgraph we also answer the question which k-trees are cover-incomparability graphs and which chordal graphs without K"4 are cover-incomparability graphs.

In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let $G$ be an $r$-colorable graph and let $P\subset V(G)$. Albertson [J.\ Combin.\ Theory Ser. B \textbf{73} (1998), 189--194] has proved that if every pair of vertices in $P$ have distance at least four, then every $(r+1)$-coloring of $G[P]$ can be extended to an $(r+1)$-coloring of $G$, where $G[P]$ is the subgraph of $G$ induced by $P$. In this paper, we allow $P$ to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of $G[P]$. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore [J.\ Combin.\ Theory Ser. B \textbf{77} (1999) 83--95].

This paper studies distance-based clique relaxations in unit disk graphs arising in wireless networking applications. Namely, a 2-clique is a subset of nodes with pairwise distance at most two in the graph, and a 2-club is a subset of nodes inducing a subgraph of diameter two. It is shown that in a unit disk graph any 2-clique is 4-dominated and any 2-club is 3-dominated. The former observation is used to develop a 1 2 -approximation algorithm for the maximum 2-clique problem in unit disk graphs. Moreover, this also implies polynomial solvability of the minimum dominating set problem in unit disk graphs of diameter two, whereas the same problem is shown to be hard in general diameter-two graphs. The paper also poses several related open questions of interest.

Let m t ? be the largest rational number such that every bridgeless cubic graph G associated with a positive weight ω has t perfect matchings { M 1 , ? , M t } with ω ( ? i = 1 t M i ) ? m t ? ω ( G ) . It is conjectured in this paper that m 3 ? = 4 5 , m 4 ? = 14 15 , and m 5 ? = 1 , which are called the weighted PM-covering conjectures. The counterparts of this new invariant m t ? and conjectures for unweighted cubic graphs were introduced by Kaiser et?al. (2006). It is observed in this paper that the Berge-Fulkerson conjecture implies the weighted PM-covering conjectures. Each of the weighted PM-covering conjectures is further proved to imply the Fan-Raspaud conjecture. Furthermore, a 3PM-coverage index ? (respectively, ? ? for the weighted case) is introduced for measuring the maximum ratio of the number of (respectively, the total weight of) edges covered by three perfect matchings in bridgeless cubic graphs and assessing how far a snark is from being 3-edge-colorable. It is proved that the determination of ? ? for bridgeless cubic graphs is an N P -complete problem.

We address the problem of covering points with orthogonal polygons. Specifically, given a set of n points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex polygon, if any, can be done in O(nlogn) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input.

This paper extends known results on the existence, number and structure of antichains and completely separating systems. Both these structures are classified in several ways, and both an enumeration and listing of each type of object are given in a catalogue, which is described in detail in this paper. The antichain catalogue provides a complete listing of all non-isomorphic antichains on m points for m@?7.

In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result in characterizations of all facet defining 0/+/-1-inequalities for the hop constrained chain polytope and all facet defining 0/1-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper by Dahl and Gouveia in 2004.

In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented. It is based on oriented matroid theory, a setting in which the combinatorial structural properties of these geometric features, such as incidence, order, partitioning, separation, and convexity, can be represented and analyzed in a coordinate-free manner. Projective transformations in computer vision keep in general the convexity property which implies an invariant oriented matroid representation of the planar geometric features under this class of transformations. As long as points and lines are in general position, the oriented matroid representation is also insensitive to small changes in the geometric image features. However the oriented matroid representation depends on the labeling of its elements. Checking the structural equivalence of the above mentioned geometric features represented by means of oriented matroids implies establishing whether two oriented matroid representations are equivalent up to relabeling of their elements. This is the oriented matroid isomorphism problem which is solved in this paper by means of a canonical labeling of the elements.

Let F be a family of subsets of an n-element set. Sperner's theorem says that if there is no inclusion among the members of F then the largest family under this condition is the one containing all @?n2@?-element subsets. The present paper surveys certain generalizations of this theorem. The maximum size of F is to be found under the condition that a certain configuration is excluded. The configuration here is always described by inclusions. More formally, let P be a poset. The maximum size of a family F which does not contain P as a (not-necessarily induced) subposet is denoted by La(n,P). 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.

We define a bipolar weighted digraph as a weighted digraph together with the sign function on the arcs such that the weight of each arc lies between 0 and 1, and no two parallel arcs have the same sign. Bipolar weighted digraphs are utilized to model so-called fuzzy cognitive maps, which are used in science, engineering, and the social sciences to represent the causal structure of a body of knowledge. It has been noted in the literature that a transitive closure of a bipolar weighted digraph contains useful new information for the fuzzy cognitive map it models.In this paper we ask two questions: what is a sensible and useful definition of transitive closure of a bipolar weighted digraph, and how do we compute it? We give two answers to each of these questions, that is, we present two distinct models. First, we give a review of the fuzzy digraph model, which has been, in a different form and less rigorously, studied previously in the fuzzy systems literature. Second, we carefully develop a probabilistic model, which is related to the notion of network reliability.This paper is intended for a mathematical audience.

The total domination number of a graph $G$ without isolated vertices is the minimum number of vertices that dominate all vertices in $G$. The total bondage number $b_t(G)$ of $G$ is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An $(n,m)$-grid graph $G_{n,m}$ is defined as the cartesian product of two paths $P_n$ and $P_m$. This paper determines the exact values of $b_t(G_{n,2})$ and $b_t(G_{n,3})$, and establishes some upper bounds of $b_t(G_{n,4})$., Comment: 15 pages with 4 figures

Testable weighted graph parameters and equivalent notions of testability are investigated based on papers of Laszlo Lovasz and coauthors. We prove that certain balanced minimum multiway cut densities are testable. Using this fact, quadratic programming techniques are applied to approximate some of these quantities. The problem is related to cluster analysis and statistical physics. Convergence of special noisy graph sequences is also discussed., 24 pages, short version was a contributed paper of the conference: Fete of Combinatorics and Computer Science, Keszthely, Hungary, August 11-15, 2008

In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fully dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs.

Recently, Chan et?al. introduced geodesic-pancyclic graphs H.C. Chan, J.M. Chang, Y.L.?Wang, S.J. Horng, Geodesic-pancyclic graphs, Discrete Applied Mathematics 155 (15) (2007) 1971-1978] and weakly geodesic pancyclicity H.C. Chan, J.M. Chang, Y.L.?Wang, S.J. Horng, Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Applied Mathematics and Computation 207 (2009) 333-339]. Hsu et?al. proposed a new cycle-embedding property called balanced pancyclicity H.C. Hsu, P.L. Lai, C.H.?Tsai, Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227-232]. For a graph G ( V , E ) and any two vertices x and y of V , a cycle R containing x and y can be divided into two paths, P t 1 and P t 2 , joining x and y such that len ( P t 1 ) ? len ( P t 2 ) , where len ( λ ) denotes the length of the path λ . A geodesic cycle contains P t 1 , which is the shortest path joining x and y in G , whereas, in a balanced cycle of an even (respectively, odd) length, len ( P t 1 ) = len ( P t 2 ) (respectively, len ( P t 1 ) = len ( P t 2 ) - 1 ). A graph is weakly geodesic pancyclic (respectively, balanced pancyclic) if every two vertices x and y are contained in a geodesic cycle (respectively, balanced cycle) from Max ( 3 , 2 Dist ( x , y ) ) to N , where N is the order of the graph. The interconnection network considered in this paper is the generalized base- b hypercube, which is an attractive variant of the well-known hypercube. In fact, the generalized base- b hypercube is the Cartesian product of complete graphs with b vertices. The generalized base- b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study weakly geodesic pancyclicity and balanced pancyclicity of the generalized base- b hypercube. We show that the generalized base- b hypercube is weakly geodesic pancyclic for b ? 3 and balanced pancyclic for b ? 4 .

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

Suppose that e is an edge of a graph G. Denote by me(G) the number of vertices of G that are not equidistant from both ends of e. Then the vertex PI index of G is defined as the summation of me(G) over all edges e of G. In this paper we give the explicit expressions for the vertex PI indices of four sums of two graphs in terms of other indices of two individual graphs, which correct the main results in a paper published in Ars Combin. 98 (2011).

The competition graph of a digraph, introduced by Cohen in 1968, has been extensively studied. More recently, in 2000, Cho, Kim, and Nam defined the m-step competition graph. In this paper, we offer another generalization of the competition graph. We define the (1,2)-step competition graph of a digraph D, denoted C"1","2(D), as the graph on V(D) where {x,y}@?E(C"1","2(D)) if and only if there exists a vertex z x,y, such that either d"D"-"y(x,z)=1 and d"D"-"x(y,z)@?2 or d"D"-"x(y,z)=1 and d"D"-"y(x,z)@?2. In this paper, we characterize the (1,2)-step competition graphs of tournaments and extend our results to the (i,k)-step competition graph of a tournament.

The domination invariant has played an important part in reliability theory. While most of the work in this field has been restricted to various types of network system models, many of the results can be generalized to much wider families of systems associated with matroids. Previous papers have explored the relation between undirected network systems and matroids. In this paper the main focus is on directed network systems and their relation to oriented matroids. An oriented matroid is a special type of matroid where the circuits are signed sets. Using these signed sets one can e.g., obtain a set theoretic representation of the direction of the edges of a directed network system. Classical results for directed network systems include the fact that the signed domination is either +1 or −1 if the network is acyclic, and zero otherwise. It turns out that these results can be generalized to systems derived from oriented matroids. Several classes of systems for which the generalized results hold will be discussed. These include oriented versions of k-out-of-n systems and a certain class of systems associated with matrices.