Search

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path receive the same color. For a connected graph G, the proper connection number p c ( G ) of G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one proper path in G. Recently, Li and Magnant in [8] posed the following conjecture: If G is a connected noncomplete graph of order n ≥ 5 and minimum degree δ ( G ) ≥ n / 4 , then p c ( G ) = 2 . In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if G is a connected bipartite graph of order n ≥ 4 with δ ( G ) ≥ n + 6 8 , then p c ( G ) = 2 . more...

Let k be a positive integer. In this paper, we prove that for a graph G with at least 4 k vertices, if max { d ( x ) , d ( y ) } ≥ 2 k for any pair of nonadjacent vertices { x , y } ⊆ V ( G ) , then G contains k disjoint cycles. This generalizes the results given by Corra di and Hajnal (1963), Enomoto (1998), and Wang (1999). more...

The vertices of Kneser graph K ( n , k ) are the subsets of { 1 , 2 , … , n } of cardinality k , two vertices are adjacent if and only if they are disjoint. The square G 2 of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2. Z. Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when n = 2 k + 1 . It is believed that χ ( K 2 ( 2 k + 1 , k ) ) = 2 k + c where c is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: 8 k ∕ 3 + 20 ∕ 3 for 1 k ≥ 3 (Kim and Park, 2014) and 32 k ∕ 15 + 32 for k ≥ 7 (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to χ ( K 2 ( 2 k + 1 , k ) ) ≤ 5 k ∕ 2 + c , where c is a constant in { 5 ∕ 2 , 9 ∕ 2 , 5 , 6 } , depending on k ≥ 2 . more...

The decycling number ∇ ( G ) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycle. A decycling set containing exactly ∇ ( G ) vertices of G is called a ∇ -set. For any decycling set S of a k -regular graph G , we show that | S | = β ( G ) + m ( S ) k − 1 , where β ( G ) is the cycle rank of G , m ( S ) = c + | E ( S ) | − 1 is the margin number of S , c and | E ( S ) | are, respectively, the number of components of G − S and the number of edges in G [ S ] . In particular, for any ∇ -set S of a 3-regular graph G , we prove that m ( S ) = ξ ( G ) , where ξ ( G ) is the Betti deficiency of G . This implies that the decycling number of a 3-regular graph G is β ( G ) + ξ ( G ) 2 . Hence ∇ ( G ) = ⌈ β ( G ) 2 ⌉ for a 3-regular upper-embeddable graph G , which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute Z ( G ) , the cardinality of a maximum nonseparating independent set in a 3 -regular graph G , which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph G , we show that for any ∇ -set S of G , there exists a spanning tree T of G such that the elements of S are simply the leaves of T with at most two exceptions providing ∇ ( G ) = ⌈ β ( G ) 3 ⌉ . On the other hand, if G is a loopless graph on n vertices with maximum degree at most 4 , then ∇ ( G ) ≤ n + 1 2 , if G is 4-regular , n 2 , otherwise . The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006). more...

Let G be a simple connected graph. Denote the Kirchhoff index and the degree-Kirchhoff index of G by K f ( G ) and K f ∗ ( G ) , respectively. This paper considers the asymptotic behavior of K f ( T k ( G ) ) and K f ∗ ( T k ( G ) ) of the iterated total graph T k ( G ) of an r -regular graph G . We show that the asymptotic behavior of these indices is independent of the structure of G and only dependent on the degree and the number of vertices of G . more...

An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph G , denoted by pc ( G ) , is the smallest number of colours that are needed in order to make G properly connected. Our main result is the following: Let G be a connected graph of order n and k ≥ 2 . If | E ( G ) | ≥ n − k − 1 2 + k + 2 , then pc ( G ) ≤ k except when k = 2 and G ∈ { G 1 , G 2 } , where G 1 = K 1 ∨ ( 2 K 1 + K 2 ) and G 2 = K 1 ∨ ( K 1 + 2 K 2 ) . more...

Basic definitions are given in the next paragraph. We study second clique graphs of suspensions of graphs, K 2 ( S ( G ) ) , and characterize them, in terms of an auxiliary biclique operator B which transforms a graph G into its biclique graph B(G). The characterization is then: K 2 ( S ( G ) ) ≅ B ( K ( G ) ) . We found a characterization of the graphs, G, that maximize | B ( G ) | for any given order n = | G | . This particular version of a biclique operator is new in the literature. The main motivation to study B(G) is an attempt to characterize the graphs G that maximize | K 2 ( G ) | , thus mimicking a result of Moon and Moser [12] that characterizes the graphs maximizing | K ( G ) | . The clique graph K(G) of a a graph G is the intersection graph of the set of all (maximal) cliques of G (and K 2 ( G ) = K ( K ( G ) ) ). The suspension S(G) of a graph G is the graph obtained from G by adding two new vertices which are adjacent to all other vertices, but not to each other. Here, a biclique (X, Y ) is an ordered pair of not necessarily disjoint subsets of vertices of G such that each x ∈ X is adjacent or equal to every y ∈ Y and such that (X, Y ) is maximal under component-wise inclusion. Finally B(G) is the graph whose vertices are the bicliques of G with adjacencies given by ( X , Y ) ≃ ( X ′ , Y ′ ) if and only if X ∩ X ′ ≠ ∅ or Y ∩ Y ′ ≠ ∅ . more...

Let G be a graph. A set S of vertices in Gdominates the graph if every vertex of G is either in S or a neighbor of a vertex in S. Finding a minimum cardinality set which dominates the graph is an NP-complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5, by proving that a graph belonging to this family is well-dominated if and only if it is well-covered.Assume that a weight function w is defined on the vertices of G. Then G is w-well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w-well-dominated is a vector space, and denote that vector space by WWD(G). We show that WWD(G) is a subspace of WCW(G), the vector space of weight functions w such that G is w-well-covered. We provide a polynomial characterization of WWD(G) for the case that G does not contain cycles of lengths 4, 5, and 6. more...

The linear 2-arboricity la2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose components are paths of length at most 2. In this paper, we prove that every planar graph G with =10 has la2(G)9. Using this result, we correct an error in the proof of a result in Wang (2016), which says that every planar graph G satisfies la2(G)(+1)2+6. more...

The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$-vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$. It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$, thus answering an open problem from [Gastineau, Togni, $S$-packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$, then $\left\lfloor \chi_{\rho}(G)/2 \right\rfloor +1 \le \chi_{\rho}(S_e(G)) \le \chi_{\rho}(G)+1$., Comment: 11 pages, 4 figures more...

In 2008, it is shown that if HK1,3 (the claw), then every H-free graph G has an even factor if and only if (G)2 and every odd branch-bond of G having an edge-branch. In this paper, we characterize all connected graphs H with order at least three such that every H-free graph has an even factor if and only if (G)2 and every odd branch-bond of G has an edge-branch. more...

The energy E ( G ) of a graph G is the sum of the absolute values of all eigenvalues of G . In this paper, we give a lower bound and an upper bound for graph energy in terms of vertex cover number. For a graph G with vertex cover number τ , it is proved that 2 τ − 2 c ≤ E ( G ) ≤ 2 τ Δ , where c is the number of odd cycles in G and Δ is the maximum vertex degree of G . The lower bound is attained if and only if G is the disjoint union of some complete bipartite graphs with perfect matchings and some isolated vertices, the upper bound is attained if and only if G is the disjoint union of τ copies of K 1 , Δ together with some isolated vertices. more...

A k-block in a graph G is a maximal set of at least k vertices no two of which can be separated in G by removing less than k vertices. It is separable if there exists a tree-decomposition of adhesion less than k of G in which this k-block appears as a part. Carmesin et al. proved that every finite graph has a canonical tree-decomposition of adhesion less than k that distinguishes all its k-blocks and tangles of order k. We construct such tree-decompositions with the additional property that every separable k-block is equal to the unique part in which it is contained. This proves a conjecture of Diestel. more...

Graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ź { 3 , . . . , n } . A vertex v ź V ( G ) is called super-heavy if the number of its neighbours in G is at least ( n + 1 ) / 2 . The complete bipartite graph K 1 , 3 is called a claw.For a given graph H we say that G is H-c1-heavy if for every induced subgraph K of G isomorphic to H and every maximal clique C in K there is a super-heavy vertex in every non-trivial component of K - C ; and that G is H-o1-heavy if in every induced subgraph of G isomorphic to H there are two non-adjacent vertices with sum of degrees at least | G | + 1 . Let Z 1 denote a graph consisting of a triangle with a pendant edge. In this paper we prove that every 2-connected K 1 , 3 -o1-heavy and Z 1 -c1-heavy graph is pancyclic. As a consequence we obtain a complete characterization of graphs H such that every 2-connected graph claw-o1-heavy and H-c1-heavy graph is pancyclic. This result extends previous work by Bedrossian 1. We give a new sufficient condition for pancyclicity of 2-connected graphs.Ore-type degree condition restricted to induced claws is involved.As well as some other degree condition on induced modified claws.Result extends the previous work by Bedrossian. more...

The non-commuting graph Γ(G) of group G is a graph with the vertex set G − Z(G) and two distinct vertices x and y are adjacent whenever xy = yx. In this paper, we compute the spectrum of non-commuting graphs of some wellknown groups. Further, if G is a non-abelian finite group and its non-commuting graph Γ(G) is k−regular, then we prove k = 2sq where q is an odd prime. more...

A w-container Cw(u,v) of a graph G between two distinct vertices u and v is a set of w disjoint paths between u and v. A w-container Cw(u,v) is a w-container if every vertex of G is on some path in Cw(u,v). A graph G is said to be w-connected if there exists a w-container between any two distinct vertices u and v. The connectivity of the arrangement graph An,k is k(nk). In this paper, we prove that An,k is k(nk)-connected for nk2. We review some properties of the arrangement graph.We prove that there exists a set of disjoint paths in an incomplete arrangement graph.We prove that the arrangement graph An,k is k(nk)-connected for nk2. more...

In this paper, we obtain two spectral upper bounds for the $k$-independence number of a graph which is is the maximum size of a set of vertices at pairwise distance greater than $k$. We construct graphs that attain equality for our first bound and show that our second bound compares favorably to previous bounds on the $k$-independence number., The manuscript has been improved by comments from the referees. To appear in Linear Algebra and its Applications more...

An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a graph G, denoted by pc(G), is the smallest number of colours that are needed in order to make G properly connected. In this paper we consider sufficient conditions in terms of the ratio between minimum degree and order of a 2-connected graph G implying that G has proper connection number 2. more...

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer b ( G ) for which G has a b-coloring with b ( G ) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval [ χ ( G ) , b ( G ) ] . It is known that not all graphs are b-continuous. Here, we show that if G has girth at least 10, then G is b-continuous. more...

Given a finite group G, we denote by Δ(G) the commuting graph of G which is defined as follows: the vertex set is G and two distinct vertices x and y are joined by an edge if and only if xy = yx. C... more...

The weight of an edge x y of a graph G is deg G ( x ) + deg G ( y ) and the weight of G is the minimum over all weights of edges of G . The problem of finding the maximum weight of a graph having n vertices and m edges was posed by Erd?s in 1990 and completely solved by Jendrol'?and Schiermeyer in 2001. This paper deals with a modification of the above problem, in which involved graphs are connected and of size m ( n 2 ) - ( ? n / 2 ? 2 ) . The maximum weight is determined for all admissible pairs ( n , m ) . more...

Let integers r � 2 and d � 3 be fixed. Let G d be the set of graphs with no induced path on d vertices. We study the problem of packing k vertex-disjoint copies of K 1 , r ( k � 2 ) into a graph G from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph G � G d can be reduced, in polynomial time, to a graph G ' � G d with O ( k ) vertices such that G has at least k vertex-disjoint copies of K 1 , r if and only if G ' has. Such a result is known for arbitrary graphs G when r = 2 and we conjecture that it holds for every r � 2 . Packing r-stars in a graph with no long induced paths.Parameter is the number k of r-stars.Linear-vertex kernel.Conjecture for the general case. more...

The eccentric distance sum (EDS) of a connected graph G is defined as ? d ( G ) = ? v ? V G ( e G ( u ) + e G ( v ) ) d G ( u , v ) , where e G ( ? ) is the eccentricity of the corresponding vertex and d G ( u , v ) is the distance between the vertices u and v . The eccentric distance sum is a novel graph invariant with vast potential in structure activity/property relationships. In this paper, the relationship between the EDS and some other graph parameters such as the order, the size, the diameter and the connectivity are studied. First, the sharp lower bound on the EDS of n -vertex connected triangle-free graphs is determined. Second, a sharp lower bound on the EDS of n -vertex connected graphs of size m is characterized. Then, a sharp lower bound on the EDS of n -vertex connected graph with given diameter is determined. At last, a sharp upper bound on the EDS of n -vertex graph with given (even) connectivity is determined. more...

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

Let G = (V (G ),E (G )) be a simple undirected graph. The reinforcement number of a graph is a vulnerability parameter of a graph. We have investigated a refinement that involves the average lower reinforcement number of this parameter. The lower reinforcement number , denoted by r e ∗ (G ), is the minimum cardinality of reinforcement set in G that contains the edge e ∗ of the complement graph G . The average lower reinforcement number of G is defined by r av (G)=1/|E(G )| ∑e* * ∈ E (G ) r e* (G ) .In this paper, we define the average lower reinforcement number of a graph and we present the exact values for some well−known graph families. more...

For a subset S of vertices of a graph G , let I G 0 ( S ) = S , I G 1 ( S ) = { v : v ?lies?on?a?shortest?path between?two?vertices?of? S } , and I G k ( S ) = I G 1 ( I G k - 1 ( S ) ) for k ? 2 . If S = I G 1 ( S ) then S is said to be a convex set. The convex hull H G ( S ) of S is the smallest convex set containing S .In this paper we study the geodetic iteration number of a graph G , defined as the smallest integer k such that H G ( S ) = I G k ( S ) for every S ? V ( G ) . The concept of geodetic iteration number is thus related to the interpretation of I G k ( S ) in the context of graph convexity. Computing the sequence I G 1 ( S ) , I G 2 ( S ) , ? can be viewed as a special type of graph dynamics, i.e.,?the process of iteratively performing applications of a well-defined operator that eventually converges to a fixed point (the convex hull H G ( S ) ). Therefore, the geodetic iteration number is a natural graph invariant that tells us the minimum number of iterations to guarantee the convergence of any initial subset, providing a measure of nonconvexity of the convex space defined over the graph.For each positive integer k , we give a forbidden induced subgraph characterization of distance-hereditary graphs with geodetic iteration number at most k . Distance-hereditary graphs play an important role in the study of geodesic convexity, since for such graphs the distances between vertices are preserved in connected induced subgraphs. As a consequence of our results, we describe a polynomial-time algorithm for the computation of g i n ( G ) when G is a distance-hereditary graph. more...

A k-ranking of a graph G is a labeling of the vertices of G with values from {1,...,k} such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of G is the smallest value of k for which a k-ranking of G exists. The graph G is k-critical if it has tree-depth k and every proper minor of G has smaller tree-depth. We establish partial results in support of two conjectures about the order and maximum degree of k-critical graphs. As part of these results, we define a graph G to be 1-unique if for every vertex v in G, there exists an optimal ranking of G in which v is the unique vertex with label 1. We show that several classes of k-critical graphs are 1-unique, and we conjecture that the property holds for all k-critical graphs. Generalizing a previously known construction for trees, we exhibit an inductive construction that uses 1-unique k-critical graphs to generate large classes of critical graphs having a given tree-depth., Comment: 14 pages, 4 figures more...

We present a neighborhood condition for a graph to be super k-restricted edge-connected.The main result generalizes some existing results on super k-restricted edge-connectivity for k = 1 , 2 , (see 7,8).The main result improves the sufficient condition on λ k -optimal graph, which is published in Discrete Mathematics (see 14). An edge cut S of a connected graph G = ( V , E ) is a k-restricted edge cut if every component of G - S contains at least k vertices. A graph is said to be super k-restricted edge-connected if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. Let k be a positive integer, and let G be a connected triangle-free graph of order n ? 2 k . In this paper, we prove that if the minimum degree ? ( G ) ? k + 1 - ( - 1 ) k and there are at least k + 1 + ( - 1 ) k 2 common vertices in the neighbor sets of each pair of nonadjacent vertices in G, then G is super k-restricted edge-connected. more...

A (p, q)-graph G is said to be (1, N)-arithmetic if there is a function from the vertex set V(G) to so that the values obtained as the sums of the labeling assigned to their end vertices, can be ar... more...

A set D ? V ( G ) of a graph G is a dominating set if every vertex v ? V ( G ) is either in D or adjacent to a vertex in D . The domination number γ ( G ) of a graph G is the minimum cardinality of a dominating set of G . Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n -vertex maximal outerplanar graph having t vertices of degree 2, then γ ( G ) ? n + t 4 . We improve their upper bound by showing γ ( G ) ? n + k 4 , where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that γ ( G ) ? 5 n 16 for a Hamiltonian maximal planar graph G with n ? 7 vertices. more...

Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W 1 , W 2 , ? , W k be the sets of vertices of the k connected components in G - B (where B is a set of blue vertices). If w ? W i is the only white neighbor of some b ? B in the graph G B ? W i , then we change w to blue. A minimum positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue and has minimum cardinality. The PSD propagation time of a PSDZFS B of graph G is the minimum number of iterations that it takes to color the entire graph blue, starting with B blue, such that at each iteration as many vertices are colored blue as allowed by the color-change rule. The minimum and maximum PSD propagation times are taken over all minimum PSD zero forcing sets of the graph. It is conjectured that every propagation time between the minimum and maximum propagation time is attainable by some minimum PSDZFS (this is not the case for the standard color-change rule). Tools are developed that aid in the computation of PSD propagation time. Several graph families and graphs with extreme PSD propagation times ( | G | - 2 , | G | - 1 , 1 , 0 ) are analyzed. more...

The maximum average degree of a graph G, denoted by mad ( G ) , is defined as mad ( G ) = max H ? G ? 2 e ( H ) v ( H ) . Suppose that ? is an orientation of G, G ? denotes the oriented graph. It is well-known that for any graph G, there exists an orientation ? such that Δ + ( G ? ) ? k if and only if mad ( G ) ? 2 k .A graph is called a pseudoforest if it contains at most one cycle in each component, is d-bounded if it has maximum degree at most d. In this paper, it is proven that, for any non-negative integers k and d, if G is a graph with mad ( G ) ? 2 k + 2 d k + d + 1 , then G decomposes into k + 1 pseudoforests with one being d-bounded. This result in some sense is analogous to the Nine Dragon Tree (NDT) Conjecture, which is a refinement of the famous Nash-Williams Theorem that characterizes the decomposition of a graph into forests. A class of examples is also presented to show the sharpness of our result. more...

For a graph G , let O ( G ) denote the set of odd degree vertices of G . A graph G is collapsible if for any subset R ? V ( G ) with | R | ? 0 (mod 2), G has a spanning connected subgraph H R such that O ( H R ) = R . The reduction of G is the graph obtained from G by contracting all maximally collapsible subgraphs until no collapsible subgraph is left. Let G be a graph on n ? 8 vertices. In this paper, we prove that if d ( x ) + d ( y ) ? n - 2 - p ( n ) for each x y ? E ( G ) , then G is collapsible or G is one of 43 special graphs or the reduction of G is K 1 , t where t ? 2 or G is a class of well-characterized graphs, where p ( n ) = 0 for n even and p ( n ) = 1 for n odd, which generalizes the earlier results by Catlin (1987), and by Li and Yang (2012). more...

There are numerous results bounding the circumference of certain 3-connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3-connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3-connected graph with at least n vertices contains a - or -minor. This result implies that the size of the largest bond in a 3-connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3-connected graph by showing that any 3-connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3-connected planar or cubic graph on n vertices. Then for any , G has a -minor with , and thus a bond of size at least . more...

A b-coloring of a graph is a proper coloring of its vertices such that every color class contains a vertex that has neighbors in all other color classes. The b-chromatic number of a graph is the largest integer b ( G ) such that the graph has a b-coloring with b ( G ) colors. This metric is upper bounded by the largest integer m ( G ) for which G has at least m ( G ) vertices with degree at least m ( G ) - 1 . There are a number of results reporting that graphs with high girth have high b-chromatic number when compared to m ( G ) . Here, we prove that every graph with girth at least 7 has b-chromatic number at least m ( G ) - 1 . Our proof also yields a polynomial algorithm that produces an optimal b-coloring of these graphs. more...

A clique of a graph G is a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G . The clique-transversal number, denoted by ? c ( G ) , is the cardinality of a minimum clique-transversal set in G . Wang et?al. (2014) proved that ? c ( G ) = ? n 3 ? for any 2-connected { K 1 , 3 , K 4 } -free 4-regular graph of order n , and conjectured that ? c ( G ) ? 10 n + 3 27 for a connected { K 1 , 3 , K 4 } -free 4-regular graph of order n .In this paper, we give a short proof of the aforementioned theorem of Wang et?al. and show that the above conjecture is true, apart from only three exceptions. more...

Let G be a k-connected graph, and T be a subset of V (G). If G-T is not connected, then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with |T| = k. Let T be a k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G1 and G2 such that |G1| ≥ 2, |G2| ≥ 2, then we call T a nontrivial k-cut-set of G. Suppose that G is a (k -1)-connected graph without nontrivial (k -1)-cut-set. Then we call G a quasi k-connected graph. In this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph without K−4, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least \(\frac{{|V(G)|}}{2}\) edges of G such that the contraction of every member of them results in a quasi k-connected graph. more...

graph G (V, E) is said to be Hamiltonian if it contains a spanning cycle. The spanning cycle is called a Hamiltonian cycle of G and G is said to be a Hamiltonian graph. A Hamiltonian path is a path that contains all the vertices in V (G) but does not return to the vertex in which it began. In this paper, we study Hamiltonicity of 3-connected, 3-regular planar bipartite graph G with partite sets V=M  N. We shall prove that G has a Hamiltonian cycle if G is balanced with M = N. For that we present an algorithm for a bipartite graph KM,N where M>3, N>3 and M,N both are even to possess a Hamiltonian cycle. In particular, we also prove a theorem for S proper subset (M or N) of V the number of components W (G-S) = S implies the graph has a Hamiltonian path. more...

A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share the same color. An edge-colored graph is (strongly) rainbow connected if there exists a rainbow (geodesic) path between every pair of vertices. The (strong) rainbow connection number of G, denoted by ( scr ( G ) , respectively) rc ( G ) , is the smallest number of colors that are needed in order to make G (strongly) rainbow connected. A vertex-colored graph G is rainbow vertex-connected if any pair of vertices in G are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G, denoted by rvc ( G ) , is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Though for a general graph G it is NP-Complete to decide whether rc ( G ) = 2 (or rvc ( G ) = 2 ), in this paper, we show that the problem becomes easy when G is a bipartite graph. Whereas deciding whether rc ( G ) = 3 (or rvc ( G ) = 3 ) is still NP-Complete, even when G is a bipartite graph. Moreover, it is known that deciding whether a given edge(vertex)-colored (with an unbound number of colors) graph is rainbow (vertex-) connected is NP-Complete. We will prove that it is still NP-Complete even when the edge(vertex)-colored graph is bipartite. We also show that a few NP-hard problems on rainbow connection are indeed NP-Complete. more...

The minimum rank mr(G) of a simple graph G is de nedto be the smallest possible rank over all symmetric real matrices whose(i;j)-th entry (for i 6= j) is nonzero whenever fi;jgis an edge in G and iszero otherwise. The corona C n K t is obtained by joining all the verticesof the complete graph K t to each n vertex of the cycle C n . For any t,we obtain an upper bound of zero forcing number of L(C n K t ), the linegraph of C n K t , and get some bounds of mr(L(C n K t )). Specially fort = 1;2, we have calculated mr(L(C n K t )) by the cut-vertex reductionmethod. 1. Introduction and preliminariesLet S n denote the set of real symmetric n n matrices. A graph G = (V;E)means a simple undirected graph (an edge is a two-element subset of vertices).For A = (a i;j ) 2S n , the graph of A, denoted G(A), is the graph with verticesf1;:::;ngand edges ffi;jgja i;j 6= 0 and i 6= jg. Note that the diagonal of Ais ignored in determining G(A). The set of symmetric matrices described by Gis S(G) = fA 2S more...

Let T be an edge-weighted tree and let d min , d max be two nonnegative real numbers. The pairwise compatibility graph (PCG) of T is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent in G if and only if the weighted distance between their corresponding leaves in T is in the interval d min , d max . Similarly, a given graph G is a PCG if there exist suitable T , d min , d max , such that G is a PCG of T. Yanhaona, Bayzid and Rahman proved that there exists a graph with 15 vertices that is not a PCG. On the other hand, Calamoneri, Frascaria and Sinaimeri proved that every graph with at most seven vertices is a PCG. In this paper we construct a graph of eight vertices that is not a PCG, which strengthens the result of Yanhaona, Bayzid and Rahman, and implies optimality of the result of Calamoneri, Frascaria and Sinaimeri. We then construct a planar graph with sixteen vertices that is not a PCG. Finally, we prove a variant of the PCG recognition problem to be NP-complete. more...

A function f : V ( G ) → { 1 , … , k } is a (proper) k -colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1 , for every edge u v ∈ E ( G ) . The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k -colouring of G . Given a graph G and a subgraph H of G , a circular q -backbone k -colouring f of ( G , H ) is a k -colouring of G such that q ≤ ∣ f ( u ) − f ( v ) ∣ ≤ k − q , for each edge u v ∈ E ( H ) . The circular q -backbone chromatic number of a graph pair ( G , H ) , denoted CBC q ( G , H ) , is the minimum k such that ( G , H ) admits a circular q -backbone k -colouring. Inspired by Steinberg’s conjecture, we conjecture that if G is a planar graph containing no cycles on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 6 . In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 7 . Then, we prove that if H ⊆ G is a forest whose connected components are paths, then CBC 2 ( G , H ) ≤ 6 . more...

For a simple connected undirected graph G = (V;E), the Wiener index W (G) of G is defined as half the sum of the shortest-path distances between all pairs of vertices u;v of G. The kth power of a graph G, denoted by G k , is a graph with the same vertex set as G such that two vertices are adjacent in G k if and only if their distance is at most k in G. Let Pn be a path on n vertices. In this paper, for the graph G = Pn2Pn, we obtain a closed form expression for W (G 2 ). In addition, a correct closed form expression is stated forW (P 3 more...

The $k$th power $G^k$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^k$ if the distance between $u$ and $v$ in $G$ is at most $k$. Let $\chi(H)$ and $\chi_l(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called {\em chromatic-choosable} if $\chi_l (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer $k$ such that $G^k$ is chromatic-choosable for every graph $G$. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether $G^2$ is chromatic-choosable for every graph $G$. Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and unbounded size. In this paper, we answer Zhu's question by showing that for every integer $k \geq 2$, there exists a graph $G$ such that $G^k$ is not chromatic-choosable. Moreover, for any fixed $k$ we show that the value $\chi_l(G^k) - \chi(G^k)$ can be arbitrarily large., Comment: 11 pages more...

Let G = ( V , E ) be a connected graph. The locating-chromatic number of G , denoted by χ L ( G ), is the cardinality of a minimum locating coloring of the vertex set V ( G ) such that all vertices have distinct coordinates. The results on locating-chromatic number of graphs are still limited. In particular, the locating-chromatic number of trees is not completely solved. Therefore, in this paper, we study the locating-chromatic number of any binary tree. more...

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager. Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1/m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\geq n$. The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\geq n/2$, which is best possible. In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph and the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1-o(1))$., Comment: 16 pages, 2 figures. Updated to show that Theorem 2 also applies to infinite graphs. Accepted for publication in Discrete Mathematics more...

The spectrum allocation problem in wireless communications can be modeled through vertex labelings of a graph, wherein each vertex represents a transmitter and edges connect vertices whose corresponding transmitters are operating in close proximity. One well-known model is the L ( 2 , 1 ) -labeling of a graph G in which a function f maps the vertices of G to the nonnegative integers such that if vertices x and y are adjacent, then | f ( x ) − f ( y ) | ≥ 2 , and if x and y are at distance two, then | f ( x ) − f ( y ) | ≥ 1 . The λ -number of G is the minimum span over all L ( 2 , 1 ) -labelings of G . Informally, an amalgamation of two graphs G 1 and G 2 along a fixed graph G 0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G 0 , one in G 1 and the other in G 2 . In this work, we supply a tight upper bound for the λ -number of amalgamations of several Cartesian products of complete graphs along a complete graph and find the exact λ -numbers for certain infinite subclasses of amalgamations of this form. A surprising relationship between the former upper bound and the minimum makespan scheduling problem is highlighted. more...

An L(2,1)-labeling of a graph G = (V, E) is a function f from the vertex set V (G) to the set of non-negative integers such that adjacent vertices get numbers at least two apart, and vertices at distance two get distinct numbers. The L(2,1)- labeling number denoted by λ2,1(G) of G is the minimum range of labels over all such labeling. In this article, it is shown that, for an interval graph G, the upper bound of λ2,1(G)is � +ω,whereand ωrepresentsthemaximumdegreeoftheverticesand size of maximum clique respectively. An O(m + n) time algorithm is also designed to L(2,1)-label a connected interval graph, where m and n represent the number of edges and vertices respectively. Extending this idea it is shown that λ2,1(G) ≤ � +3ω for circular-arc graph. more...

A graph H has the hourglass property if in every induced hourglass S (the unique simple graph with the degree sequence (4, 2, 2, 2, 2)), there are two non-adjacent vertices which have a common neighbor in H-V(S). Let G be a claw-free simple graph and k a positive integer. In this paper, we prove that if either G is hourglass-free or G has the hourglass property and @d(G)>=4, then G has a 2-factor with at most k components if and only if it has an even factor with at most k components. We provide some of its applications: combining the result (the case when k=1) with Jaeger (1979) and Chen et al. (2006), we obtain that every 4-edge-connected claw-free graph with the hourglass property is hamiltonian and that every essentially 4-edge-connected claw-free hourglass-free graph of minimum degree at least three is hamiltonian, thereby generalizing the main result in Kaiser et al. (2005) and the result in Broersma et al. (2001) respectively in which the conditions on the vertex-connectivity are replaced by the condition of (essential) 4-edge-connectivity. Combining our result with Catlin and Lai (1990), Lai et al. (2010) and Paulraja (1987), we also obtain several other results on the existence of a hamiltonian cycle in claw-free graphs in this paper. more...

An edge-colored graph G is rainbow connected if every two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G , denoted by rc ( G ) , is the smallest number of colors that are needed in order to make G rainbow connected. It was proved that computing rc ( G ) is an NP-hard problem, as well as that even deciding whether a graph has rc ( G ) = 2 is NP-complete. Li et al. proved that rc ( G ) ⩽ 5 if G is a bridgeless graph with diameter 2, while rc ( G ) ⩽ 9 if G is a bridgeless graph with diameter 3. Furthermore, Uchizawa et al. showed that determining the rainbow connection number of graphs is strongly NP-complete even for outerplanar graphs. In this paper, we give upper bounds of the rainbow connection number of outerplanar graphs with small diameters. more...