Search

The issues of ruggedness and vulnerability are cruxes in network security research, which must be considered during the network designing phase. Parameters such as toughness, isolated toughness, and binding number characterize the vulnerable of the network from the structure of networks. The path factor, a special case of the generalized ℋ‐factor, measures the feasibility of data transmission in networks. Recent advances have been obtained to show that there is an inevitable connection between the vulnerability parameters of the network and the existence of path factors, while we found that some existing theoretical results are not tight and there is still a long way for further improvement. In view of graph theory approaches, this paper mainly contributes to determine the sharp bounds of toughness, isolated toughness, and binding number for the existence of path factor in different settings, and therefore solve the open problems left unsolved in previous articles. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n and k an integer not great than n. Erdős and Sós conjectured that if G has at least n ( k − 2 ) / 2 edges, then G contains all trees of order k. Loebl, Komlós and Sós conjectured that if at least n / 2 vertices of G have degree at least k − 1 , then G contains all trees of order k. In this paper, it is shown that both the conjectures are true for graphs with independence number two, and our results generalize some known results. [ABSTRACT FROM AUTHOR]

As an efficient theoretical tool, graph theory is widely used in computing chemistry. In terms of index computation on molecular graphs, the researchers can learn the potential properties of chemical compounds, including drugs, materials, and organics. In this paper, by means of distance computation, we study the eccentric version indices of cycloalkanes which occur quite frequently in the chemical drugs and other compounds. The promising prospects of the application for the physical, chemical, medical, and pharmacy engineering are illustrated by theoretical conclusions obtained in this article. [ABSTRACT FROM AUTHOR]

Given two graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1, G_2)$$ is the smallest integer $$N$$ such that, for any graph $$G$$ of order $$N$$ , either $$G_1$$ is a subgraph of $$G$$ , or $$G_2$$ is a subgraph of the complement of $$G$$ . We consider the case that $$G_1$$ is a cycle and $$G_2$$ is a (generalized) wheel. We expand the knowledge on exact values of Ramsey numbers in three directions: large cycles versus wheels of odd order; large wheels versus cycles of even order; and large cycles versus generalized odd wheels. [ABSTRACT FROM AUTHOR]

We consider proper edge colorings of a graph G using colors of the set { 1 , … , k } . Such a coloring is called neighbor sum distinguishing if for any u v ∈ E ( G ) , the sum of colors of the edges incident to u is different from the sum of the colors of the edges incident to v . The smallest value of k in such a coloring of G is denoted by ndi Σ ( G ) . Let mad ( G ) and Δ ( G ) denote the maximum average degree and the maximum degree of a graph G , respectively. In this paper we show that, for a graph G without isolated edges, if mad ( G ) < 8 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 1 , 7 } ; and if mad ( G ) < 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 2 , 7 } . [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n ≥ 3 . The remoteness ρ = ρ ( G ) is the maximum, over all vertices, of the average distance from a vertex to all others. The radius r = r ( G ) is the minimum, over all vertices, of the eccentricity of a vertex. Aouchiche and Hansen (2011) conjectured that ρ − r ≥ 3 − n 4 if n is odd and ρ − r ≥ 2 n − n 2 4 ( n − 1 ) if n is even. In this paper, we confirm this conjecture. In addition, we completely characterize extremal graphs attaining the lower bound. [ABSTRACT FROM AUTHOR]

Let $G$ be a graph of order $n\geq 6$ with minimum degree ${\it\delta}(G)\geq 4$. Arkin and Hassin [‘Graph partitions with minimum degree constraints’, Discrete Math. 190 (1998), 55–65] conjectured that there exists a bipartition $S,T$ of $V(G)$ such that $\lfloor n/2\rfloor -2\leq S,T\leq \lceil n/2\rceil +2$ and the minimum degrees in the subgraphs induced by $S$ and $T$ are at least two. In this paper, we first show that $G$ has a bipartition such that the minimum degree in each part is at least two, and then prove that the conjecture is true if the complement of $G$ contains no complete bipartite graph $K_{3,r}$, where $r=\lfloor n/2\rfloor -3$. [ABSTRACT FROM AUTHOR]

Abstract: For two given graphs and , the planar Ramsey number is the smallest integer such that for any planar graph on vertices, either contains or its complement contains . Let denote a cycle of length and a complete graph of order . Sun, Yang, Lin and Song conjectured that and the conjecture was proved for . In this paper, it is shown that which confirms the conjecture for . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . Surahmat, Baskoro and Tomescu conjectured that for odd, and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

Abstract: A graph is 3-domination-critical (3-critical, for short), if its domination number is 3 and the addition of any edge decreases by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 271 (2003) 1–12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European Journal of Combinatorics 23 (2002) 777–784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph is Hamilton-connected if and only if , where is the toughness of . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length and a complete graph of order . In this paper, it is shown that . [Copyright &y& Elsevier]

Abstract: Let be a graph. A signed dominating function on G is a function such that for each , where is the closed neighborhood of . The weight of a signed dominating function f is . A signed dominating function f is minimal if there exists no signed dominating function g such that and for each . The upper signed domination number of a graph G, denoted by , equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in [O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287–293] and [C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193–197], respectively. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length and a complete graph of order . In this paper we show that for and , with the former result confirming a conjecture due to Erdös, Faudree, Rousseau and Schelp that for and in the case where . [Copyright &y& Elsevier]

Abstract: A graph G is 3-domination critical if its domination number is 3 and the addition of any edge decreases by 1. Let G be a 3-domination critical graph with toughness more than one. It was proved that G is Hamilton-connected for the cases [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Math. 271 (2003) 1–12] and [Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European J. Combin. 23 (2002) 777–784]. In this paper, we show G is Hamilton-connected for the case . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length m and a complete graph of order . It was conjectured that for and . We show that and , and the latter result confirms the conjecture in the case when . [Copyright &y& Elsevier]

Abstract: Let denote a tree of order and a wheel of order . In this paper, we show the Ramsey numbers for , where if , if or and , and otherwise; for . [Copyright &y& Elsevier]

Abstract: A subset of the vertex set of a graph is called acyclic if the subgraph it induces in contains no cycles. is called an acyclic dominating set of if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by , is called the acyclic domination number of . Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151–165] introduced the concept of acyclic domination and posed the following open problem: if is the minimum degree of , is for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive , there is a graph with diameter two such that . [Copyright &y& Elsevier]

Abstract: A graph G is said to be cyclable if for each orientation D of G, there exists a set such that reversing all the arcs with one end in S results in a hamiltonian digraph. Let G be 4-connected simple graph of even order . In this paper, we show that if for any with , then G is cyclable. [Copyright &y& Elsevier]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest positive integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Sn denote a star of order n and Wm a wheel of order m+1. This paper shows that R(Sn,W6)=2n+1 for n≥3 and R(Sn,Wm)=3n-2 for m odd and n≥m-1≥2. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . In this paper, we show that for odd, and , which was conjectured by Surahmat, Baskoro and Tomescu. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that for even , and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

In this paper, we study the upper size Ramsey number u ( G 1 , G 2 ) , defined by Erdős and Faudree, as well as the star-critical Ramsey number r ∗ ( G 1 , G 2 ) , defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u ( n K k , m K l ) and r ∗ ( n K k , m K l ) for k , l ≥ 3 and large m , n ; u ( C n , C m ) for m odd, with n > m ≥ 3 ; and r ∗ ( C n , C m ) for m odd, with n ≥ m ≥ 3 and ( m , n ) ≠ ( 3 , 3 ) . [ABSTRACT FROM AUTHOR]

Abstract: Given two graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or its complement contains . Let denote a cycle of order and a wheel of order . In this paper, it is shown that for odd, and , and for odd and . [Copyright &y& Elsevier]