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

Affine equivalent classes and extended affine equivalent (EA-equivalent for short) classes of vectorial Boolean functions have important applications in cryptography, logic circuit, sequences for communications, etc. Recently, Y. Zhang et al., computed the number of affine equivalent classes of n -variable Boolean functions when 1 ≤ n ≤ 10 by group isomorphism (Zhang et al., 2016). However, the case for affine equivalent vectorial Boolean function remains a challenging open problem. Furthermore, little result for EA-equivalent vectorial Boolean function is known except a trivial lower bound mentioned in Mullen and Panario (2013, P246). In this paper, we focus on the challenging problem of calculating the number of affine equivalent classes and EA-equivalent classes of vectorial Boolean functions. First, for EA-equivalence, we prove that the trivial lower bound proposed in Mullen and Panario (2013) has at least 3 effective figures if n is not too small. We then show that the lower bound also holds for affine equivalent classes. Furthermore, we give an explicit formula and calculate the exact number of affine equivalent classes of ( n , m ) -functions with 1 ≤ m , n ≤ 11 by GAP. The results in this paper are helpful for the theory and applications of the classifications of vectorial Boolean functions.

Well-graded families, extremal systems and maximum systems (the last two in the sense of VC-theory and Sauer-Shelah lemma on VC-dimension) are three important classes of set systems. This paper aims to study the notion of duality in the context of these classes of set systems and then use the obtained results for studying graphs. More specifically, we are concerned with the characterization of the finite set systems which themselves and their dual systems are both well-graded, extremal or maximum. On the way to this goal, and maybe also of independent interest, we study the structure of the well-graded families with the property that the size of the system is not much bigger than the size of its essential domain, that is, the set of elements of the domain which are shattered by the system as single element subsets. As another target of the paper, we use the above results to characterize graphs whose set systems of open or closed neighbourhoods, cliques or independent sets are well-graded, extremal or maximum. We clarify the relation of such graphs to the celebrated half-graphs. Through the paper, we frequently relate our investigations to the VC-dimension of the systems. Also we use one-inclusion graphs associated to set systems as an important technical tool., Comment: 32 pages

In this paper, we firstly introduce a kind of weightwise almost perfectly balanced Boolean functions. And then, a construction of weightwise perfectly balanced Boolean functions on 2 q + 2 variables is given by modifying the support of the weightwise almost perfectly balanced functions, where q is a non-negative integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper.

In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a “relaxed” form of triangle inequality called the biased triangle inequality. We denote this problem as the Biased-TSP-Path . In this paper, we prove that the Biased-TSP-Path is approximable within a constant factor. Specifically, we design a 4-approximation algorithm by a suitable modification of the double-tree algorithm using effective shortcutting procedures.

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.

Zero-difference balanced (ZDB) functions were introduced by Ding in connection with constructions of optimal constant composition codes and optimal and perfect difference systems of sets. Based on such functions, people have constructed optimal constant weight codes and optimal frequency-hopping sequences. In order to obtain more optimal cryptographic objects, the zero-difference balanced (ZDB) function is generalized to the near zero-difference balanced (N-ZDB) function in the present paper, whose characterizations are partially given. Furthermore, we prove that near zero-difference balanced (N-ZDB) functions are equivalent to partitioned almost difference families (PADFs) in design theory. As the main contribution of this paper, three classes of the N-ZDB functions are proposed by means of the partition of Z n , where n is an odd positive integer. Employing these N-ZDB functions, we obtain at the same time optimal frequency-hopping sequences and optimal difference systems of sets with flexible parameters.

Recently, linear codes with few weights have been widely studied, since they have applications in data storage systems, communication systems and consumer electronics. In this paper, we present a class of three-weight and five-weight linear codes over Fp, where p is an odd prime and Fp denotes a finite field with p elements. The weight distributions of the linear codes constructed in this paper are also settled. Moreover, the linear codes illustrated in the paper may have applications in secret sharing schemes., Comment: 19 pages

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.

We prove the determinant connectivity matrix formula. Mathematically, the proof introduces novel techniques based on an algebraic approach and connectivity properties. Although this is the second part of a previous paper and has its original motivation there, the paper is self contained and the result is interesting in itself.

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.

Bitprobe complexity of the static membership problem has been widely investigated since Burhman et al. (2000) studied the worst-case bounds for a whole range of membership problems. Though tremendous progress has been made in recent years, as is evident from the remarkable papers due to Alon and Feige (2009) [1] , Viola (2012) [8] , and Lewenstein et al. (2014), among others, Nicholson et al. (2013) [5] in their survey of the state of the art of the area noted that even the first non-trivial scenario of two probe adaptive schemes storing two elements of the universe is not completely settled, in that the lower bound for this problem is still open. We propose a proof (Kesh and Sharma, 2019) [3] for the lower bound for the same problem, but for a restricted class of schemes. We believe that this proof makes progress over the ideas proposed by Radhakrishnan et al. (2001, 2010) towards the proof. It is our belief that the single restriction imposed on the general class of schemes towards our proof faithfully captures the dependencies among the elements that share the same bit in the datastructure, and we hope that the general lower bound proof can be developed using similar ideas.

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).

This paper studies the family of graphs with broadcast time equal to their diameter. The diametral broadcast graph (dbg) problem is to answer the question whether for a given n and d a graph on n vertices can be constructed whose diameter and broadcast time are equal to d . This paper presents several dbg constructions. Together, they solve the dbg problem for all the possible combinations of values of n and d . We also define the diametral broadcast function D B ( n , d ) as the minimum possible number of edges in a dbg on n vertices and diameter d . We describe all the trees on n vertices with diametral broadcast time. These trees give the exact value for D B ( n , d ) when tree based dbg construction is possible. For the general case we give an upper bound on D B ( n , d ) .

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.