Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has ...Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.展开更多
Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations ...Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.展开更多
A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge ...A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.展开更多
The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,...The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.展开更多
A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if t...A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.展开更多
Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 fo...Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.展开更多
Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is les...Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.展开更多
Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of ...Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.展开更多
A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider...A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.展开更多
Two problems for task schedules in a multiprocessor parallel system are discussed in Ans paper (1) given a partially ordered set of tasks represented by the venices of an acyclic directed graph with their correspondin...Two problems for task schedules in a multiprocessor parallel system are discussed in Ans paper (1) given a partially ordered set of tasks represented by the venices of an acyclic directed graph with their corresponding processing bines, derive the lower bound on the Annimum time(LBMT) needed to process the task graph for a given number of processors. (2) Determine the lower bound on minimum number of processors(LBMP) needed to complete those tasks in minimum bine. It is shown that the proposed LBMT is sharper than previously Known values and the comPUtational aspeCts of these bounds are also discussed.展开更多
The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the ...The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the graphs for which the bounds are attained. Moreover, some known lower bounds on the spectral radius and the Laplacian spectral radius of unweighted graphs can be deduced from the bounds.展开更多
基金Supported by the National Natural Science Foundation of China(11471077)the Open Research Fund of Key Laboratory of Spatial Data Mining and Information Sharing of MOE(2018LSDMIS09)Foundation of Key Laboratory of Intelligent Metro of Universities in Fujian Province(53001703)
文摘Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.
基金Supported by the National Natural Science Foundation of China(10771080)by the Fund of Fuzhou Uni-versity(XRC-0956)by the Natural Science Foundation of Fujian Province(2010J05005)
文摘Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.
基金Supported by the National Natural Science Foundation of China(10971198)the Zhejiang Natural Science Foundation of China(Z6110786)
文摘A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.
基金Supported by the National Natural Science Foundation of China(11071272,10831001,11171279,11101087)the Young Talent Foundation of Fuzhou University(XRC-1154)
文摘The atom-bond connectivity（ABC） index provides a good model for the stability of linear and branched alkanes as well as the strain energy of cycloalkanes,which is defined as ABC（G） =∑ uv∈E（G） √d u＋dv-2 dudv,where du denotes the degree of a vertex u in G.A chemical graph is a graph in which no vertex has degree greater than 4.In this paper,we obtain the sharp upper and lower bounds on ABC index of chemical bicyclic graphs.
文摘A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.
基金supported by the National Natural Science Foundation of China (Grant No.10571117)the Development Foundation of Shanghai Municipal Education Commission (Grant No.05AZ04)
文摘Let G = (V,E) be a simple graph without isolated vertices. For positive integer k, a 3-valued function f : V → {-1,0,1} is said to be a minus total k-subdominating function (MTkSF) if sum from (u∈N(v)) to f(u)≥1 for at least k vertices v in G, where N(v) is the open neighborhood of v. The minus total k-subdomination number γkt(G) equals the minimum weight of an MTkSF on G. In this paper, the values on the minus total k-subdomination number of some special graphs are investigated. Several lower bounds on γkt of general graphs and trees are obtained.
文摘Let be a simple graph with vertex set V and edge set E. A function is said to be a reverse total signed vertex dominating function if for every , the sum of function values over v and the elements incident to v is less than zero. In this paper, we present some upper bounds of reverse total signed vertex domination number of a graph and the exact values of reverse total signed vertex domination number of circles, paths and stars are given.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571117）, and the Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘Given a graph G, a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and ｜C｜ ≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as τC（G）, is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques in G have nonempty intersection. Let F be a class of graphs G such that F = {G｜ K（G） is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus τC（G）/｜G｜ ≤ 1/2 for all G ∈F.
基金supported by the Minister of Science and Higher Education of Poland (Grant No. JP2010009070)
文摘A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.
文摘Two problems for task schedules in a multiprocessor parallel system are discussed in Ans paper (1) given a partially ordered set of tasks represented by the venices of an acyclic directed graph with their corresponding processing bines, derive the lower bound on the Annimum time(LBMT) needed to process the task graph for a given number of processors. (2) Determine the lower bound on minimum number of processors(LBMP) needed to complete those tasks in minimum bine. It is shown that the proposed LBMT is sharper than previously Known values and the comPUtational aspeCts of these bounds are also discussed.
基金supported by the National Natural Science Foundation of China(Nos.11101027,11071115,10971114,10990011,11171097)the Fundamental Research Funds for the Central Universities of China(No.2011JBM136)
文摘The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the graphs for which the bounds are attained. Moreover, some known lower bounds on the spectral radius and the Laplacian spectral radius of unweighted graphs can be deduced from the bounds.
