This paper presents an optimisatiombased verification process for obstacle avoidance systems of a unicycle-like mobile robot. It is a novel approach for the collision avoidance verification process. Local and global o...This paper presents an optimisatiombased verification process for obstacle avoidance systems of a unicycle-like mobile robot. It is a novel approach for the collision avoidance verification process. Local and global optimisation based verification processes are developed to find the worst-case parameters and the worst-case distance between the robot and an obstacle. The kinematic and dynamic model of the unicycle-like mobile robot is first introduced with force and torque as the inputs. The design of the control system is split into two parts. One is velocity and rotation using the robot dynamics, and the other is the incremental motion planning for robot kinematics. The artificial potential field method is chosen as a path planning and obstacle avoidance candidate technique for verification study as it is simple and widely used. Different optimisation algorithms are applied and compared for the purpose of verification. It is shown that even for a simple case study where only mass and inertia variations are considered, a local optimization based verification method may fail to identify the worst case. Two global optimisation methods have been investigated： genetic algorithms （GAs） and GLOBAL algorithms. Both of these methods successfully find the worst case. The verification process confirms that the obstacle avoidance algorithm functions correctly in the presence of all the possible parameter variations.展开更多
This paper discusses about balancing control of unicycle robot.Unicycle robot consists of pitch which acts like inverted pendulum and roll which acts like reaction wheel pendulum.The robot which does not have actuator...This paper discusses about balancing control of unicycle robot.Unicycle robot consists of pitch which acts like inverted pendulum and roll which acts like reaction wheel pendulum.The robot which does not have actuator located in yaw axis is made to derive the simple dynamics.Lagrange equation is applied to deriving dynamic equations.Obtained dynamic equations are used to design the sliding mode control.State variables of the designed control are pitch angle and roll angle.Sliding mode control has chattering problem,which is eliminated by using the sigmoid function as switching function.Finally the control performance and eliminated chattering problem is verified by simulation.展开更多
The concept of an intelligent control system for a complex nonlinear biomechanical system of an extension cableless robotic unicycle discussed.A thermodynamic approach to study optimal control processes in complex non...The concept of an intelligent control system for a complex nonlinear biomechanical system of an extension cableless robotic unicycle discussed.A thermodynamic approach to study optimal control processes in complex nonlinear dynamic systems applied.The results of stochastic simulation of a fuzzy intelligent control system for various types of external/internal excitations for a dynamic,globally unstable control object-extension cableless robotic unicycle based on Soft Computing(Computational Intelligence Toolkit-SCOptKBTM)technology presented.A new approach to design an intelligent control system based on the principle of the minimum entropy production(minimum of useful resource losses)determination in the movement of the control object and the control system is developed.This determination as a fitness function in the genetic algorithm is used to achieve robust control of a robotic unicycle.An algorithm for entropy production computing and representation of their relationship with the Lyapunov function(a measure of stochastic robust stability)described.展开更多
Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is s...Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is studied. It is proved a piecewise linear function of the order and edge size of the hypergraph.展开更多
Technically, a group of more than two wheeled mobile robots working collectively towards a common goal are known as a multi-robot system. An increasing number of industries have implemented multi-robot systems to elim...Technically, a group of more than two wheeled mobile robots working collectively towards a common goal are known as a multi-robot system. An increasing number of industries have implemented multi-robot systems to eliminate the risk of human injuries while working on hazardous tasks, and to improve productivity. Globally, engineers are continuously researching better, simple, and faster cooperative Control algorithms to provide a Control strategy where each agent in the robot formation can communicate effectively and achieve a consensus in their position, orientation and speed.<span style="font-family:Verdana;"> </span><span style="font-family:Verdana;">This paper explores a novel Formation Building Algorithm and its global stability around a configuration vector. A simulation in MATLAB</span><sup><span style="font-size:12px;font-family:Verdana;"><span lang="ZH-CN" style="font-size:12pt;font-family:宋体;">?</span></span></sup><span style="font-family:Verdana;"> was carried out to examine the performance of the Algorithm for two geometric formations and a fixed number of robots. In addition, an obstacle avoidance technique was presented assuming that all robots are equipped with range sensors. In particular, a uniform rounded obstacle is used to analyze</span><span style="font-family:Verdana;"> </span><span style="font-family:Verdana;">the performance of the technique with the use of detailed geometric calculations.</span>展开更多
The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U...The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U)∈(n,n+1] are characterized.展开更多
The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the comple...The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.展开更多
Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its compleme...Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its complement respectively.Lanzhou index Lz(G)can be expressed as(n-1)M_(1)(G)-F(G),where M_(1)(G)and F(G)denote the first Zagreb index and the forgotten index of G respectively,and n is the number of vertices in G.It turns out that Lanzhou index outperforms M_(1)(G)and F(G)in predicting the logarithm of the octanol-water partition coefficient for octane and nonane isomers.It was shown that stars and balanced double stars are the minimal and maximal trees for Lanzhou index respectively.In this paper,we determine the unicyclic graphs and the unicyclic chemical graphs with the minimum and maximum Lanzhou indices separately.展开更多
In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wie...In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. Discrete Appl. Math., 2014, 171：35 41）, and give a simple way to compare the Wiener index and the Zagreb indices for trees. Moreover, the comparison between the Wiener index and the Zagreb indices for unicyclic graphs is carried out.展开更多
A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken ove...A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.展开更多
The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper we show the expression of the nullity and nullity set of unicyclic graphs with n vertices and girth r, and characterize ...The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper we show the expression of the nullity and nullity set of unicyclic graphs with n vertices and girth r, and characterize the unicyclic graphs with extremal nullity.展开更多
In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the ab...In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.展开更多
This paper first elaborates the research situation and progress of Laplace characteristics and the eigenvalues value of graphs. The second is given an upper bound of characteristic value of a kind of special graph usi...This paper first elaborates the research situation and progress of Laplace characteristics and the eigenvalues value of graphs. The second is given an upper bound of characteristic value of a kind of special graph using the properties of similar matrices. At the same time, a new upper bound of Laplace characteristic values are given using properties of Laplace matrix and the similarity matrix, to improve the existing results. Then, we use the example of the upper bound of our results are more precise than some previous results. Finally the use Laplace non- zero eigenvalues of graph properties to give a bound expressions using the degree of square with a number of edges and the graph of the number, number of connected component expression map, it reflected the relationship between eigenvalues and the amount of Laplace.展开更多
Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G ly...Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G lying closer to vertex u than to vertex u,the number of edges of G lying closer to vertex than to vertex u and the number of edges of G at the same distance to u and u,respectively.In this paper,by transformation and calculation,the lower bound of revised edge-Szeged index of unicyclic graphs with given diameter is obtained,and the extremal graph is depicted.展开更多
In this paper,we determine graphs with the largest Laplacian spectral radius among the unicyclic and the bicyclic graphs on n vertices with k pendant vertices,respectively.
The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.
We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having...We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues.展开更多
Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with...Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with the root of a rooted tree T_(i)of order n_(i)for each i=1,2,…,g,where n_(i)≥1 and∑^(g)_(i=1)n_(i)=n.In this note,the graph with the minimal least eigenvalue(and the graph with maximal spread)in C(T_(1),T_(2),…,T_(g))is determined.展开更多
It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and g...It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and girth g. In 1987, Cao proved that this conjecture is true for k ≥ g（g - 2）/8 and false for k = 2 and sufficiently large g. In this note, we show that g 〉12 suffices for the counterexample and give more counterexamples with large girth for any integer k 〉 1.展开更多
A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic the...A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.展开更多
文摘This paper presents an optimisatiombased verification process for obstacle avoidance systems of a unicycle-like mobile robot. It is a novel approach for the collision avoidance verification process. Local and global optimisation based verification processes are developed to find the worst-case parameters and the worst-case distance between the robot and an obstacle. The kinematic and dynamic model of the unicycle-like mobile robot is first introduced with force and torque as the inputs. The design of the control system is split into two parts. One is velocity and rotation using the robot dynamics, and the other is the incremental motion planning for robot kinematics. The artificial potential field method is chosen as a path planning and obstacle avoidance candidate technique for verification study as it is simple and widely used. Different optimisation algorithms are applied and compared for the purpose of verification. It is shown that even for a simple case study where only mass and inertia variations are considered, a local optimization based verification method may fail to identify the worst case. Two global optimisation methods have been investigated： genetic algorithms （GAs） and GLOBAL algorithms. Both of these methods successfully find the worst case. The verification process confirms that the obstacle avoidance algorithm functions correctly in the presence of all the possible parameter variations.
基金The MKE(The Ministry of Knowledge Economy),Korea,under the ITRC(Infor mation Technology Research Center)support program supervised by the NIPA(National IT Industry Promotion Agency)(NIPA-2012-H0301-12-2006)the MKE,Korea,under the Human Resources Development Programfor Specialized Environment Navigation/Localization Technology Research Center support program supervised by the NIPA(NIPA-2012-H1502-12-1002)
文摘This paper discusses about balancing control of unicycle robot.Unicycle robot consists of pitch which acts like inverted pendulum and roll which acts like reaction wheel pendulum.The robot which does not have actuator located in yaw axis is made to derive the simple dynamics.Lagrange equation is applied to deriving dynamic equations.Obtained dynamic equations are used to design the sliding mode control.State variables of the designed control are pitch angle and roll angle.Sliding mode control has chattering problem,which is eliminated by using the sigmoid function as switching function.Finally the control performance and eliminated chattering problem is verified by simulation.
文摘The concept of an intelligent control system for a complex nonlinear biomechanical system of an extension cableless robotic unicycle discussed.A thermodynamic approach to study optimal control processes in complex nonlinear dynamic systems applied.The results of stochastic simulation of a fuzzy intelligent control system for various types of external/internal excitations for a dynamic,globally unstable control object-extension cableless robotic unicycle based on Soft Computing(Computational Intelligence Toolkit-SCOptKBTM)technology presented.A new approach to design an intelligent control system based on the principle of the minimum entropy production(minimum of useful resource losses)determination in the movement of the control object and the control system is developed.This determination as a fitness function in the genetic algorithm is used to achieve robust control of a robotic unicycle.An algorithm for entropy production computing and representation of their relationship with the Lyapunov function(a measure of stochastic robust stability)described.
文摘Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is studied. It is proved a piecewise linear function of the order and edge size of the hypergraph.
文摘Technically, a group of more than two wheeled mobile robots working collectively towards a common goal are known as a multi-robot system. An increasing number of industries have implemented multi-robot systems to eliminate the risk of human injuries while working on hazardous tasks, and to improve productivity. Globally, engineers are continuously researching better, simple, and faster cooperative Control algorithms to provide a Control strategy where each agent in the robot formation can communicate effectively and achieve a consensus in their position, orientation and speed.<span style="font-family:Verdana;"> </span><span style="font-family:Verdana;">This paper explores a novel Formation Building Algorithm and its global stability around a configuration vector. A simulation in MATLAB</span><sup><span style="font-size:12px;font-family:Verdana;"><span lang="ZH-CN" style="font-size:12pt;font-family:宋体;">?</span></span></sup><span style="font-family:Verdana;"> was carried out to examine the performance of the Algorithm for two geometric formations and a fixed number of robots. In addition, an obstacle avoidance technique was presented assuming that all robots are equipped with range sensors. In particular, a uniform rounded obstacle is used to analyze</span><span style="font-family:Verdana;"> </span><span style="font-family:Verdana;">the performance of the technique with the use of detailed geometric calculations.</span>
基金Supported by the project item for young teachers of colleges and universities of Anhui province( 2 0 0 3jq1 0 1 ) and the project item of Anhui University for talents group construction
文摘The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ 1(U)=n or λ 1(U)∈(n,n+1] are characterized.
基金Supported by the National Natural Science Foundation of China(11861011,11501133,11661010)。
文摘The Kirchhoff index Kf(G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf■ and the first four maximum values of Kf(ū),where ■ and ū are the complements of a tree T and unicyclic graph U, respectively.
基金Supported by the National Natural Science Foundation of China(11871256)the Chinese-Croatian bilateral project(7-22)。
文摘Very recently D.Vukicevic et al.[8]introduced a new topological index for a molecular graph G named Lanzhou index as∑_(u∈V(G))d_(u)d^(2)_(u),where d_(u)and d_(u)denote the degree of vertex u in G and in its complement respectively.Lanzhou index Lz(G)can be expressed as(n-1)M_(1)(G)-F(G),where M_(1)(G)and F(G)denote the first Zagreb index and the forgotten index of G respectively,and n is the number of vertices in G.It turns out that Lanzhou index outperforms M_(1)(G)and F(G)in predicting the logarithm of the octanol-water partition coefficient for octane and nonane isomers.It was shown that stars and balanced double stars are the minimal and maximal trees for Lanzhou index respectively.In this paper,we determine the unicyclic graphs and the unicyclic chemical graphs with the minimum and maximum Lanzhou indices separately.
基金The NSF(11301093,11501139)of Chinathe NSF(2014A030313640)of Guangdong Provincethe Foundation(Yq2014111)for Distinguished Young Talents in Higher Education of Guangdong Province
文摘In this note, we correct a wrong result in a paper of Das et al. with regard to the comparison between the Wiener index and the Zagreb indices for trees （Das K C, Jeon H, Trinajstic N. The comparison between the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. Discrete Appl. Math., 2014, 171：35 41）, and give a simple way to compare the Wiener index and the Zagreb indices for trees. Moreover, the comparison between the Wiener index and the Zagreb indices for unicyclic graphs is carried out.
文摘A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.
文摘The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper we show the expression of the nullity and nullity set of unicyclic graphs with n vertices and girth r, and characterize the unicyclic graphs with extremal nullity.
文摘In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.
文摘This paper first elaborates the research situation and progress of Laplace characteristics and the eigenvalues value of graphs. The second is given an upper bound of characteristic value of a kind of special graph using the properties of similar matrices. At the same time, a new upper bound of Laplace characteristic values are given using properties of Laplace matrix and the similarity matrix, to improve the existing results. Then, we use the example of the upper bound of our results are more precise than some previous results. Finally the use Laplace non- zero eigenvalues of graph properties to give a bound expressions using the degree of square with a number of edges and the graph of the number, number of connected component expression map, it reflected the relationship between eigenvalues and the amount of Laplace.
文摘Given a connected graph G,the revised edge-revised Szeged index is defined as Sz_(e)^(*)(G)=∑_(e=uv∈E_(G))(m_(u)(e)+m_(0)(e)/2)(m_(v)(e)+m_(0)(e)/w),where m_(u)(e),m_(v)(e)and m_(0)(e)are the number of edges of G lying closer to vertex u than to vertex u,the number of edges of G lying closer to vertex than to vertex u and the number of edges of G at the same distance to u and u,respectively.In this paper,by transformation and calculation,the lower bound of revised edge-Szeged index of unicyclic graphs with given diameter is obtained,and the extremal graph is depicted.
基金supported by National Natural Science Foundation of China (Grant No.10871204)the Fundamental Research Funds for the Central Universities (Grant No.09CX04003A)
文摘In this paper,we determine graphs with the largest Laplacian spectral radius among the unicyclic and the bicyclic graphs on n vertices with k pendant vertices,respectively.
基金Supported by the Project of Talent Introduction for Graduates of Chizhou University (Grant No2009RC011)
文摘The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.
基金This work is supported by the National Natural Science Foundation of China (grants No. 11671344, 11531011 and 11701492).
文摘We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues.
文摘Let U^(g)_(n)be the set of connected unicyclic graphs of order n and girth g.Let C(T_(1),T_(2),…,T_(g))∈U^(g)_(n)be obtained from a cycle v_(1)v_(2)…v_(g)v_(1)(in an anticlockwise direction)by identifying v_(i)with the root of a rooted tree T_(i)of order n_(i)for each i=1,2,…,g,where n_(i)≥1 and∑^(g)_(i=1)n_(i)=n.In this note,the graph with the minimal least eigenvalue(and the graph with maximal spread)in C(T_(1),T_(2),…,T_(g))is determined.
基金Supported by Tsinghua University Initiative Scientific Research Program
文摘It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g ＋ k and girth g. In 1987, Cao proved that this conjecture is true for k ≥ g（g - 2）/8 and false for k = 2 and sufficiently large g. In this note, we show that g 〉12 suffices for the counterexample and give more counterexamples with large girth for any integer k 〉 1.
基金Supported by the National Natural Science Foundation of China (10671081)
文摘A graph has exactly two main eigenvalues if and only if it is a 2-walk linear graph.In this paper,we show some necessary conditions that a 2-walk（a,b）-linear graph must obey.Using these conditions and some basic theorems in graph theory,we characterize all 2-walk linear graphs with small cyclic graphs without pendants.The results are given in sort on unicyclic,bicyclic,tricyclic graphs.
