G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to deter...G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.展开更多
Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution...Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution of more complex cases requires good understanding of the relevant part of Graph theory. Even though this is usually not covered by Physics’ curriculum, it may still be of interest to some teachers and their mathematically inclined students, who may want to learn details of the rigorous approach. The purpose of this article is to provide a concise derivation of a linear set of equations leading to a unique solution of the problem at hand. We also present a simple computer program which builds such a solution for circuits of any textbook size.展开更多
We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 ...We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.展开更多
M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + ...M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.展开更多
文摘G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.
文摘Solving for currents of an electrical circuit with resistances and batteries has always been the ultimate test of proper understanding of Kirchoff’s rules. Yet, it is hardly ever emphasized that a systematic solution of more complex cases requires good understanding of the relevant part of Graph theory. Even though this is usually not covered by Physics’ curriculum, it may still be of interest to some teachers and their mathematically inclined students, who may want to learn details of the rigorous approach. The purpose of this article is to provide a concise derivation of a linear set of equations leading to a unique solution of the problem at hand. We also present a simple computer program which builds such a solution for circuits of any textbook size.
文摘We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.
文摘M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.
基金Supported by the National Natural Science Foundation of China(11071002)the NFS of Anhui Province(11040606M14)+4 种基金the NSF of Department of Education of Anhui Province(KJ2011A195)the Program for New Century Excellent Talents in University(NCET-10-0001)the Key Project of Chinese Ministry of Education(210091)the Specialized Research Fund for the Doctoral Program of Higher Education(20103401110002)the Scientific Research Fund for Fostering Distinguished Young Scholars of Anhui University(KJJQ1001)
