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 .

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph $$G_1\square G_2$$ of graphs $$G_1$$ and $$G_2$$ satisfying that $$G_1$$ is traceable and $$G_2$$ is connected with a path factor. Let $$P_n$$ be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) $$P_n\square H$$ is Hamiltonian; (ii) $$P_n\square H$$ is 1-tough; and (iii) H has a path factor.

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.

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. We study numerous problems on split graphs, namely the k -Vertex-Disjoint Paths , k -Cycle , k -Path and k - l -Stable Set problems. In the k -Vertex-Disjoint Paths problem, we are given a graph and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k -Cycle / k -Path problem, we are given a graph and are asked whether there is a path/cycle of length k . The k - l -Stable Set problem takes a graph and an integer k as input, and asks whether the graph has a subset of k vertices such that the distance between every two vertices in the subset is at least l + 1 . It is known that all the above problems are NP-complete on split graphs. We derive a 4 k -vertex kernel for the k -Vertex-Disjoint Paths problem and an O ( k 2 ) -vertex kernel for both the k -Path problem and the k -Cycle problem. Concerning the k - l -Stable Set problem, for l = 1 or l ≥ 3 , the problem is polynomial-time solvable on split graphs. For l = 2 , we prove that the k - l -Stable Set problem is W[1]-complete on split graphs, with respect to k . However, if the given split graph contains no K 1 , r as an induced subgraph, and every vertex in the independent set of the split graph has degree at most d , we derive a linear vertex kernel for the k - 2 -Stable Set problem, where both r and d are constants.

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

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 .

We study the problem of determining the graph with n vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) 2 n ∕ 3 vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order n , for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture.

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

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 .

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

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 ′ ≠ ∅ .

A connected graph G with at least 2 m + 2 n + 2 vertices is said to satisfy the property E ( m , n ) if G contains a perfect matching and for any two sets of independent edges M and N with | M | = m and | N | = n with M ∩ N = ∅ , there is a perfect matching F in G such that M ⊂ F and N ∩ F = ∅ . In particular, if G is E ( m , 0 ) , we say that G is m -extendable. One of the authors has proved that every m -tough graph of even order at least 2 m + 2 is m -extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for m -extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee E ( m , n ) .

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.

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.

A tree T is called a k-tree if the maximum degree of T is at most k. In this paper, we give a sufficient condition for a graph to have a k-tree containing specified vertices as following: let G be a connected graph and let S be a subset of V(G). If \(\alpha _G(S)\le (k-1)\kappa _G(S)+1\), then G has a k-tree containing S. Moreover, this condition is sharp.

Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.

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.

Let $G$ be a distance-regular graph of order $v$ and size $e$. In this paper, we show that the max-cut in $G$ is at most $e(1-1/g)$, where $g$ is the odd girth of $G$. This result implies that the independence number of $G$ is at most $\frac{v}{2}(1-1/g)$. We use this fact to also study the extendability of matchings in distance-regular graphs. A graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t, Comment: 18 pages, accepted to European Journal of Combinatorics

For a connected graph G=(V,E), a subset FV is called an Rk-vertex-cut of G if GF is disconnected and each vertex in VF has at least k neighbors in GF. The cardinality of the minimum Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by k(G). The conditional connectivity is a measure to explore the structure of networks beyond the vertex-connectivity. Let Sym(n) be the symmetric group on {1,2,,n} and T be a set of transpositions of Sym(n). Denote by G(T) the graph with vertex set {1,2,,n} and edge set {ij:(ij)T}. If G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n),T) by WGn. In this paper, we determine the values of 1 and 2 for Cayley graphs generated by wheel graphs and prove that 1(WGn)=4n6 and 2(WGn)=8n18.

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

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.

A connected graph G is said to be k-connected if it has more than k vertices and remains connected whenever fewer than k vertices are deleted. In this paper, we present a tight sufficient condition for a connected graph with fixed minimum degree to be k-connected based on its spectral radius, for sufficiently large order.

This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos–Renyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source $S$ , and a destination $D$ are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of $S$ and $D$ , a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest $S$ – $D$ path as well as in a minimum $S$ – $D$ cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with $n$ nodes, where there is an edge between two nodes with probability $p$ , the optimal strategy does not depend on $p$ or $n$ , even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around $p = \ln n/n$ . The policy is efficiently implementable, requiring no more than $30\log _{2} n$ operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.

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.

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we study the proper connection number on the lexicographic, strong, Cartesian, and direct products and present exact values or upper bounds for these products of graphs.

In this paper, we investigate the algebraic connectivity of connected graphs, and determine the graph which has the minimum algebraic connectivity among all connected graphs of order $n$ with given stability number $\alpha\geq\lceil\frac{n}{2}\rceil$, or covering number, respectively.

A d -regular graph on n vertices with the second largest absolute eigenvalue at most λ is called an ( n , d , λ ) -graph. The celebrated expander mixing lemma for ( n , d , λ ) -graphs builds a connection between graph spectrum and edge distribution. In this paper, we present some applications of the expander mixing lemma. In particular, we make progress toward the toughness conjecture of Brouwer. The toughness t ( G ) of a connected graph G is defined as t ( G ) = min { | S | c ( G − S ) } , where c ( G − S ) denotes the number of components of G − S and the minimum is taken over all proper subsets S ⊂ V ( G ) such that c ( G − S ) > 1 . It has been shown that for any connected ( n , d , λ ) -graph G , t ( G ) > 1 3 ( d 2 d λ + λ 2 − 1 ) by Alon, and independently, t ( G ) > d λ − 2 by Brouwer. Brouwer also conjectured that a tight lower bound should be t ( G ) ≥ d λ − 1 for any ( n , d , λ ) -graph G . We show that t ( G ) > d λ − 2 . As the generalized vertex connectivity is closely related to graph toughness, we also present a lower bound on the generalized vertex connectivity of ( n , d , λ ) -graphs, which implies an improved result for classical vertex connectivity.

A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Between them, Chakraborty et al. [J. Comb. Optim., 2011] and Ananth et al. [FSTTCS, 2012] have shown that for every integer k, k \geq 2, it is NP-complete to decide whether a given graph can be rainbow coloured using k colours. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Chandran and Rajendraprasad have shown that the problem of deciding whether a given split graph G can be rainbow coloured using 3 colours is NP-complete and further have described a linear time algorithm to rainbow colour any split graph using at most one colour more than the optimum [COCOON, 2012]. In this article, we settle the computational complexity of the problem on split graphs and thereby discover an interesting dichotomy. Specifically, we show that the problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k \in {2,3}, but can be solved in polynomial time for all other values of k., This is the full version of a paper to be presented at ICGT 2014. This complements the results in arXiv:1205.1670 (which were presented in COCOON 2013), and both will be merged into a single journal submission

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].

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.

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.

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.

The edge-rupture degree of an incomplete connected graph G is defined as r ' ( G ) = m a x { ω ( G - S ) - | S | - m ( G - S ) : S ź E ( G ) , ω ( G - S ) 1 } , where ω ( G - S ) and m ( G - S ) , respectively, denote the number of components and the order of a largest component in G - S . This is a reasonable parameter to measure the vulnerability of networks, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. In this paper, firstly, the relationships between the edge-rupture degree and some other graph parameters, namely the edge-connectivity, edge-integrity, edge-toughness, edge-tenacity, diameter, the algebraic connectivity and the minimum degree are established. After that, the edge-rupture degree of the middle graphs of path and cycle are given. Then, we introduced the concept of r'-maximal graph and give some basic results of such graphs. Finally, we introduce the concept of edge-ruptured and strictly edge-ruptured graph, and we establish necessary and sufficient conditions for a graph to be edge-ruptured and strictly edge-ruptured, respectively.

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.

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

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.

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.

Computing k-edge connected components can be used to capture closely related vertices in a graph. It is an important problem with many applications. Due to the high time complexities of traditional algorithms for computing k-edge connected components, it is difficult for them to be applied to efficiently process large scale graphs. In this paper, an early merging and splitting based maximal k-edge connected subgraph detection algorithm, named MSK, is proposed. It computes the k-edge connected components of a graph with an order list of vertices which is decided according to the connectivity of vertices in the graph. During the processing of the vertex list, if two vertices are k-edge connected, they are merged into a super-vertex. On the contrary , if the vertex pair does not satisfy the condition of k-edge connectivity, the related vertices and edges are removed from the graph, and the graph is decomposed into several subgraphs. The above steps are performed iteratively in the obtained subgraphs until each subgraph become a k-edge connected component. In order to further improve the time efficiency, an approximate algorithm PMSK is also proposed. The experimental results on a large number of real and synthetic graphs show that the proposed algorithms are accurate and more efficient than the state-of-the-art algorithms.

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 connectivity and forbidden subgraphs, implying a graph to have proper connection number 2.

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

For a connected graph G, a set S of vertices is a cyclic vertex cutset if G−S is not connected and at least two components contain a cycle respectively. The cyclic vertex connectivity is the cardinality of a minimum cyclic vertex cutset. In this paper, for any k-regular graph G with girth g and the number of vertices, we give a sufficient condition for the cyclic vertex connectivity . Then we give a polynomial time algorithm to determine for a cubic graph G. The time complexity of the algorithm is bounded by .

Let G be a graph and let s be a vertex of G. We consider the structure of the set of all lifts of two edges incident with s that preserve edge-connectivity. Mader proved that two mild hypotheses imply there is at least one pair that lifts, while Frank showed (with the same hypotheses) that there are at least $$(\deg (s)-1)/2$$(deg(s)-1)/2 disjoint pairs that lift. We consider the lifting graph: its vertices are the edges incident with s, two being adjacent if they form a liftable pair. We have three main results, the first two with the same hypotheses as for Mader's Theorem. (i) Let F be a subset of the edges incident with s. We show that F is independent in the lifting graph of G if and only if there is a single edge-cut C in G of size at most $$r+1$$r+1 containing all the edges in F, where r is the maximum number of edge-disjoint paths from a vertex (not s) in one component of $$G-C$$G-C to a vertex (not s) in another component of $$G-C$$G-C. (ii) In the k-lifting graph, two edges incident with s are adjacent if their lifting leaves the resulting graph with the property that any two vertices different from s are joined by k pairwise edge-disjoint paths. If both $$\deg (s)$$deg(s) and k are even, then the k-lifting graph is a connected complete multipartite graph. In all other cases, there are at most two components. If there are exactly two components, then each component is a complete multipartite graph. If $$\deg (s)$$deg(s) is odd and there are two components, then one component is a single vertex. (iii) Huck proved that if k is odd and G is $$(k+1)$$(k+1)-edge-connected, then G is weakly k-linked (that is, for any k pairs $$\{x_i,y_i\}$${xi,yi}, there are k edge-disjoint paths $$P_i$$Pi, with $$P_i$$Pi joining $$x_i$$xi and $$y_i$$yi). We use our results to extend a slight weakening of Huck's theorem to some infinite graphs: if k is odd, every $$(k+2)$$(k+2)-edge-connected, locally finite, 1-ended, infinite graph is weakly k-linked.

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. The anti-Ramsey number a r ( G , H ) is the maximum number of colors in an edge-coloring of G with no rainbow copy of H . Anti-Ramsey numbers were introduced by Erd?s et?al. (1973) and studied in numerous papers. Originally a complete graph was considered as G , but afterwards also other graphs were used as host graphs.We consider a complete split graph as the host graph and discuss some results for the graph H containing short cycles or triangles with pendant edges. Among others we show that a r ( K n + K s ? , C 3 + ) = a r ( K n + K s ? , C 3 ) = n + s - 1 for n , s ? 1 , where C 3 + denotes a triangle with a pendant edge.

Consider the family C of all connected simple graphs on n vertices which have k cut-vertices. We state some properties of the graph in C which has the minimum Kirchhoff index. In particular, we characterize this graph in the cases that k ? n 2 or k ? n - 3 . Also we characterize the graph G in C having a non-cut-vertex with the lowest resistive eccentricity index among all non-cut-vertices of all graphs in C .

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

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.

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.