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

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

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.

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

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.

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.

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

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

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

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 .

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.

A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices at distance 2 are mapped onto distinct integers. It is known that, for any fixed k>=4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for [email protected]?3. For even k>=8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k>=4 by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.

A (p,1)-total labelling of a graph G=(V,E) is a total colouring L from V@?E into {0,...,l} such that |L(v)-L(e)|>=p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p,1)-total labelling is denoted by @l"p(G). The case p=1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155-162]. In this paper we assume p>=2. It is easy to show that @l"p(G)>=@D+p-1, where @D is the maximum degree of G. Moreover, when G is bipartite, @D+p is an upper bound for @l"p(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether @l"p(G) is equal to @D+p-1 or to @D+p when G is bipartite. This is trivial when @D@?p, polynomial when @D=3 and p=2, and NP-complete in the remaining cases.

Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number = 4 having non-rank facets. The aim of the present paper is to treat the remaining case with clique number =4: we provide an infinite sequence of such webs whose stable set polytopes admit non-rank facets. s of claw-free graphs is a long-standing problem [M. Grotschel, L. Lovasz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number = 4 having non-rank facets [J. Kind, Mobilitatsmodelle fur zellulare Mobilfunknetze: Produktformen und Blockierung, Ph.D. Thesis, RWTH Aachen, 2000; G. Oriolo, Clique family inequalities for the stable set polytope for quasi-line graphs, Discrete Appl. Math. 132 (2004) 185-201; T. Liebling, G. Oriolo, B. Spille, G. Stauffer, On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs, Math. Meth. Oper. Res. 59 (2004) 25-35]. The aim of the present paper is to treat the remaining case with clique number =4: we provide an infinite sequence of such webs whose stable set polytopes admit non-rank facets.

Let $G$ be a graph and let Pm$(G)$ denote the number of perfect matchings of $G$. We denote the path with $m$ vertices by $P_m$ and the Cartesian product of graphs $G$ and $H$ by $G\times H$. In this paper, as the continuance of our paper [19], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results: 1. Let $T$ be a tree and let $C_n$ denote the cycle with $n$ vertices. Then Pm$(C_4\times T)=\prod (2+\alpha^2)$, where the product ranges over all eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)$ is always a square or double a square. 2. Let $T$ be a tree. Then Pm$(P_4\times T)=\prod (1+3\alpha^2+\alpha^4)$, where the product ranges over all non-negative eigenvalues $\alpha$ of $T$. 3. Let $T$ be a tree with a perfect matching. Then Pm$(P_3\times T)=\prod (2+\alpha^2),$ where the product ranges over all positive eigenvalues $\alpha$ of $T$. Moreover, we prove that Pm$(C_4\times T)=[{Pm}(P_3\times T)]^2$., Comment: 15 pages, 4 figures

A tensegrity graph is a graph with edges labeled as bars, cables and struts. A realization of a tensegrity graph T is a pair ( T , p ) , where p maps the vertices of T into R d for some d ≥ 1 . The realization is globally rigid if any realization ( T , q ) in R d in which the bars have the same length and the cables and struts are not longer and not shorter, respectively, is an isometric image of ( T , p ) . A tensegrity graph is weakly globally rigid in R d if it has a generic globally rigid realization in R d , and strongly globally rigid in R d if every generic realization in R d is globally rigid. In this paper we give a necessary condition for weak global rigidity in R d and prove that in the d = 1 case the same condition is also sufficient. In particular, our results imply that a tensegrity graph has a generic globally rigid realization in R 1 if and only if it has a generic universally rigid realization in R 1 . We also show that recognizing strongly globally rigid tensegrity graphs in R d is co-NP-hard for all d ≥ 1 .

Recently, the authors introduced a game invariant of graphs, called a game connectivity. In this paper, we investigate the edge version of the invariant, called a game edge-connectivity, by introducing a new combinatorial game on a graph, called a graph edge-cutting game. The game is one of generalizations of a classical combinatorial game, named the Shannon switching game. As an analog of the study of the Shannon switching game, we have a complete characterization of graphs with game edge-connectivity infinity in terms of the number of edge-disjoint spanning trees. As a corollary of the above, any graph with edge-connectivity at least 4 has game edge-connectivity infinity. Thus, since determining the game edge-connectivity of a given cubic graph is the most interesting problem, we give a useful tool to estimate the game edge-connectivity of cubic graphs. Other than those above, we study many fundamental topics of the game edge-connectivity of graphs, and propose several open problems.

Let D n be the set of digraphs with n non-isolated vertices. Let D ∈ D n and denote by d u + and d u − the outer degree and inner degree, respectively, of the vertex u of D . We define the vertex-degree-based (VDB, for short) topological index φ induced by the real numbers φ i j , as φ D = 1 2 ∑ 1 ≤ i , j ≤ n − 1 a i j φ i j , where a i j is the number of arcs in D of the form u v , where d u + = i and d v − = j . We show in this paper that this is a generalization of the concept of VDB topological indices of graphs. In the case φ i j = 1 i j , we obtain the Randic index of digraphs, which we denote by χ . We find the extremal values of χ over D n . We also find the extremal values of χ over OT ( n ) , the set of all oriented trees with n vertices. On the other hand, given a graph G , we consider the set O G of all orientations of G , and show that when G is a bipartite graph, the sink–source orientations of G uniquely attain the minimal value of χ over O G . We find the extremal values of χ over O P n and O C n , where P n and C n are the path and the cycle with n vertices, respectively. Finally, we find the extremal values of χ over O H d , the set of all orientations of the hypercube H d of dimension d .

A graph is called t -tough if the removal of any vertex set S that disconnects the graph leaves at most | S | ∕ t components. The toughness of a graph is the largest t for which the graph is t -tough. A graph is minimally t -tough if the toughness of the graph is t and the deletion of any edge from the graph decreases the toughness. The complexity class DP is the set of all languages that can be expressed as the intersection of a language in NP and a language in coNP. In this paper, we prove that recognizing minimally t -tough graphs is DP-complete for any positive rational number t . We introduce a new notion called weighted toughness, which has a key role in our proof.

In this paper we consider the following graph parameters: IR( G ), the upper irredundance number, Γ( G ), the upper domination number and β( G ), the independence number. It is well known that for any graph G , β ( G )≤ Γ ( G )≤ IR ( G ). We introduce the concept of a graph G being irredundant perfect if IR ( H )= β ( H ) for all induced subgraphs H of G . In this paper we characterize irredundant perfect graphs. This enables us to show that several classes of graphs are irredundant perfect, classes which include strongly perfect, bipartite and circular arc graphs.

This paper presents a polynomial-time algorithm for solving a restricted version of the recognition problem for bicircular matroids. Given a matroid M, the problem is to determine whether M is bicircular. Chandru, Coullard and Wagner showed that this problem is NP-hard in general. The main tool in the development of the algorithm as well as the main theoretical contribution of the paper is a set of necessary and sufficient conditions for a given matroid to be the bicircular matroid of a given graph. As a final result, the complexity result of Chandru is strenghtened.

In a 1983 paper, D. Gusfield introduced a function which is called (following W.H. Cunningham, 1985) the strength of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link, this is the function η(G) = minF⊆E(G) ∣F∣/(ω(G − F) − ω(G)), where the minimum is taken over all subsets F of E(G) such that ω(G − F), the number of components of G − F, is at least ω(G) + 1. In a 1986 paper, C. Payan introduced the fractional arboricity of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link this function is γ(G) = maxH⊆G ∣E(H)∣/(∣V(H)∣ − ω(H)), where H runs over all subgraphs of G having at least one link. Connected graphs G for which γ(G) = η(G) were used by A. Rucinski and A. Vince in 1986 while studying random graphs. We characterize the graphs and matroids G for which γ(G) = η(G). The values of γ and η are computed for certain graphs, and a recent result of Erdos (that if each edge of G lies in a C3, then ∣E(G)∣≥ 3 2 (∣V(G)∣ − 1)) is generalized in terms of η. The principal partition of a graph was introduced in 1967 by G. Kishi and Y. Kajitani, by T. Ohtsuki, Y. Ishizaki, and H. Watanabe, and by M. Iri (all of these were published in 1968). It has been used since then for the analysis of electrical networks in which the two Kirchhoff laws and Ohm's law hold, because it often allows the currents and voltage drops in the network to be completely computed with fewer measurements than are required for either of the Kirchhoff laws used alone. J. Bruno and L. Weinberg generalized the principal partition to matroids in 1971, and their generalization was refined independently by N. Tomizawa (1976) and by H. Narayanan and M.N. Vartak (1974, 1981). Here we demonstrate that γ and η are closely related to the principal partition and can be used to give a simple definition of both the principal partition and the more recent refinements of it.

Independent set games are cooperative games defined on graphs, where players are edges and the value of a coalition is the maximum cardinality of independent sets in the subgraph defined by the coalition. In this paper, we investigate the convexity of independent set games, as convex games possess many nice properties both economically and computationally. For independent set games introduced by Deng et al. (Math. Oper. Res., 24:751-766, 1999), we provide a necessary and sufficient characterization for the convexity, i.e., every non-pendant edge is incident to a pendant edge in the underlying graph. Our characterization immediately yields a polynomial time algorithm for recognizing convex instances of independent set games. Besides, we introduce a new class of independent set games and provide an efficient characterization for the convexity.

The transmission of a vertex v of a graph G is the sum of distances from v to all the other vertices in G . The Wiener complexity of G is the number of different transmissions of its vertices. Similarly, the eccentric complexity of G is defined as the number of different eccentricities of its vertices. In this paper these two complexities are compared. The complexities are first studied on Cartesian product graphs. Transmission indivisible graphs and arithmetic transmission graphs are introduced to demonstrate sharpness of upper and lower bounds on the Wiener complexity, respectively. It is shown that for almost all graphs the Wiener complexity is not smaller than the eccentric complexity. This property is proved for trees, the equality holding precisely for center-regular trees. Several families of graphs in which the complexities are equal are constructed. Using the Cartesian product, it is proved that the eccentric complexity can be arbitrarily larger than the Wiener complexity. Additional infinite families of graphs with this property are constructed by amalgamating universally diametrical graphs with center-regular trees.

Zombies and Survivor is a variant of the pursuit–evasion game Cops and Robber(s), with the difference that zombies must always move closer to the survivor. The game is played on a simple connected graph by two players. The goal of the zombies is to catch the survivor while the survivor’s objective is to avoid being captured. The zombie number of G , denoted as , is the minimum number of zombies required to capture a single survivor on G , no matter what moves the survivor make. In this paper, we prove a conjecture by Fitzpatrick et al. (2016) about the zombie number of the Cartesian product of two graphs. This result provides a new proof for . We also introduce a new problem regarding capture time in the Cartesian product of two graphs. At last, we study computational complexity of finding the zombie number of a graph G , with and without a limited capture time.

In an earlier paper entitled “Niche graphs” written by Cable, Jones, Lundgren and Seager, niche graphs were introduced and examples were provided of graphs which have niche number 0, 1, 2, and ∞. However, no examples were found of a niche graph having finite niche number 3 or larger. We still have had no success in our efforts to find such a graph. Nevertheless we have gotten some interesting results. For example, we show in this paper that if there is such a graph, then there must be one which is connected. We also show that the niche number of a graph which has a finite niche number is ≤ 2 3 |V(G)|. In addition we determine the niche number of all “wheel” graphs.

This paper studies a nondiscrete generalization of Γ ( G ), the maximum cardinality of a minimal dominating set in a graph G =( V , E ). In particular, a real-valued function ⨍: V → [ 0,1 ], is dominating if for each vertex υ ϵ V , the sum of the values assigned to the vertices in the closed neighborhood of υ , N [ υ ], is at least one, i.e., ⨍(N[υ]) ≥ 1 . The weight of a dominating function ⨍ is ⨍(V) , the sum of all values ⨍(υ) for υ ϵ V , and Γ ⨍ (G), is the maximum weight over all minimal dominating functions. In this paper we show that: (1) Γ ⨍ (G) is computable and is always a rational number; (2) the decision problems corresponding to the problems of computing Γ ( G ) and Γ ⨍ (G) are NP-complete; (3) for trees Γ ⨍ =Γ , which implies that the value of Γ ⨍ can be computed in linear time.

The eccentric-adjacency index (EAI) and the adjacent eccentric distance sum (AEDS) are two eccentricity-based graph invariants, both of which have a vast potential for predicting the physico-chemical and/or biological properties of molecules in QSAR/QSPR studies. More recently, Malik (2018) computed these two graph invariants for the join and corona products of graphs. In this paper, we present sharp upper bounds on EAI and investigate the relationship between EAI and AEDS. We first establish some sharp upper bounds on EAI for general connected graphs and quasi-trees. Then we investigate the relationship between AEDS and EAI, and we prove that AEDS > EAI for any tree with at least three vertices. Finally, we give two sufficient conditions for connected graphs satisfying the inequality AEDS > EAI and the inequality EAI > AEDS, respectively.

Suppose that we are given two independent sets I 0 and I r of a graph such that | I 0 | = | I r | , and imagine that a token is placed on each vertex in I 0 . Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I 0 into I r so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I 0 and I r with the minimum number of token movements. We finally show that one of the results for token jumping can be extended to a more generalized reconfiguration problem for independent sets, called token addition and removal .

In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend ( B 1 ) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open.

Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.

Diagnosability has played an important role in reliability of an interconnection network. In 2012, Peng et al. proposed a new measure of diagnosability, namely, g -good-neighbor diagnosability, which requires every fault-free vertex has at least g fault-free neighbors. The PMC model and MM ∗ model are widely adopted as the fault diagnosis model. The problems of g -good-neighbor diagnosability of many well-known networks under the PMC model and MM ∗ model have been widely explored. In this paper, we study the relationship between g -good-neighbor diagnosability under the PMC model and g -good-neighbor diagnosability under the MM ∗ model of a graph G . In addition, we give some sufficient conditions to ascertain g -good-neighbor diagnosability of a graph G under the PMC model and MM ∗ model. From this, many previous results can be directly obtained and g -good-neighbor diagnosability for many well-known networks under the PMC model and MM ∗ model, are derived.

This paper deals with partial binary Hadamard matrices. Although there is a fast simple way to generate about a half (which is the best asymptotic bound known so far, see de Launey (2000) and de Launey and Gordon (2001)) of a full Hadamard matrix, it cannot provide larger partial Hadamard matrices beyond this bound. In order to overcome such a limitation, we introduce a particular subgraph G t of Ito’s Hadamard Graph Δ ( 4 t ) (Ito, 1985), and study some of its properties, which facilitates that a procedure may be designed for constructing large partial Hadamard matrices. The key idea is translating the problem of extending a given clique in G t into a Constraint Satisfaction Problem, to be solved by Minion (Gent et al., 2006). Actually, iteration of this process ends with large partial Hadamard matrices, usually beyond the bound of half a full Hadamard matrix, at least as our computation capabilities have led us thus far.

A graph is a cograph if it is P 4 -free. A k -polar partition of a graph G is a partition of the set of vertices of H into parts A and B such that the subgraph induced by A is a complete multipartite graph with at most k parts, and the subgraph induced by B is a disjoint union of at most k cliques with no other edges. It is known that k -polar cographs can be characterized by a finite family of forbidden induced subgraphs, for any fixed k . A concrete family of such forbidden induced subgraphs is known for k = 1 , since 1-polar graphs are precisely split graphs. For larger k such families are not known, and Ekim, Mahadev, and de Werra explicitly asked for the family for k = 2 . In this paper we provide such a family, and show that the graphs can be obtained from four basic graphs by a natural operation that preserves 2-polarity and also preserves the condition of being a cograph. We do not know such an operation for k > 2 , nevertheless we believe that the results and methods discussed here will also be useful for higher k .

Zero forcing is a propagation process on a graph, or digraph, defined in linear algebra to provide a bound for the minimum rank problem. Independently, zero forcing was introduced in physics, computer science and network science, areas where line digraphs are frequently used as models. Zero forcing is also related to power domination, a propagation process that models the monitoring of electrical power networks. In this paper we study zero forcing in iterated line digraphs and provide a relationship between zero forcing and power domination in line digraphs. In particular, for regular iterated line digraphs we determine the minimum rank/maximum nullity, zero forcing number and power domination number, and provide constructions to attain them. We conclude that regular iterated line digraphs present optimal minimum rank/maximum nullity, zero forcing number and power domination number, and apply our results to determine those parameters on some families of digraphs often used in applications.

Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper, we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number $w$ as a self-inverting permutation $\pi^*$, an algorithm for encoding the self-inverting permutation $\pi^*$ into a reducible permutation graph $F[\pi^*]$ whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation $\pi^*$ from the reducible permutation graph $F[\pi^*]$ and the number $w$ from $\pi^*$. Both the encoding and the decoding process takes time and space linear in the length of the binary representation of $w$. The two main components of our proposed codec system, i.e., the self-inverting permutation $\pi^*$ and the reducible permutation graph $F[\pi^*]$, incorporate the binary representation of the watermark~$w$ in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph $F[\pi^*]$ and the results show that we can detect such attacks with high probability., Comment: 27 pages, 6 figures. arXiv admin note: text overlap with arXiv:1110.1194

Diagnosability is an important parameter to measure the ability of diagnosing faulty processors of a multiprocessor system. Conditional diagnosability is a realistic improvement of classical diagnosability under the condition that every processor has at least one fault-free neighboring processor. Complete-transposition graphs are proposed to be potential competitive network models of hypercubes as well as star graphs. In this paper, we show that the conditional diagnosability of the complete-transposition graph C T n under the MM ∗ model is 3 2 n ( n − 1 ) − 6 for n ≥ 7 , while the conditional diagnosability of C T n under the PMC model is 2 n ( n − 1 ) − 9 for n ≥ 5 .

Diagnosability is a significant metric to measure the reliability of multiprocessor systems. In 2012, a new measure for fault tolerance of the system was proposed by Peng et al. This measure is called the g -good-neighbor diagnosability that restrains every fault-free node to contain at least g fault-free neighbors. The Cayley graph C K n generated by the complete graph K n has many good properties as other Cayley graphs. In this paper, we show that the connectivity of C K n is n ( n − 1 ) 2 , the 1-good-neighbor connectivity of C K n is n 2 − n − 2 and the 1 -good-neighbor diagnosability of C K n under the PMC model is n 2 − n − 1 for n ≥ 4 and under the MM ∗ model is n 2 − n − 1 for n ≥ 5 .

The Turan number ex ( n , H ) is the maximum number of edges in a graph on n vertices which does not contain H as a subgraph. Gorgol gives a lower bound for ex ( n , H ) when H is the disjoint union of k copies of P 3 and conjectures this bound is tight. In this paper, we give an algorithmic proof of Gorgol’s Conjecture.

Barat and Thomassen (2006) posed the following decomposition conjecture: for each tree T , there exists a natural number k T such that, if G is a k T -edge-connected graph and | E ( G ) | is divisible by | E ( T ) | , then G admits a decomposition into copies of T . In a series of papers, Thomassen verified this conjecture for stars, some bistars, paths of length 3, and paths whose length is a power of 2. We verify this conjecture for paths of length 5.

In 2011, Janson (2011) extended the theory of graph limits to posets, defining convergence for poset sequences and proving that every such sequence has a limit object. In this paper, we focus on k -dimensional poset sequences. This restriction leads to shorter proofs and to a more intuitive limit object. As before, the limit object can be used as a model for random posets, which generalizes the well known random k -dimensional poset model. Furthermore, it can also be used to characterize a natural class of testable poset parameters.

The strong resolving graph G S R of a connected graph G was introduced in Oellermann and Peters-Fransen (2007) as a tool to study the strong metric dimension of G . Basically, it was shown that the problem of finding the strong metric dimension of G can be transformed to the problem of finding the vertex cover number of G S R . Since then, several articles on the strong metric dimension of graphs which are using this tool have been published. However, the tool itself has remained unnoticed as a properly structure. In this paper, we survey the state of knowledge on the strong resolving graphs, and also derive some new results regarding its properties.