An injective k-edge coloring of a graph G is k-edge coloringκof G such thatκ(e1)≠κ(e3)for any three consecutive edges ei,e2 and e3 of a path or a triangle.The injective chromatic index of G,denoted by x'i(G),i...An injective k-edge coloring of a graph G is k-edge coloringκof G such thatκ(e1)≠κ(e3)for any three consecutive edges ei,e2 and e3 of a path or a triangle.The injective chromatic index of G,denoted by x'i(G),is the smallest integer k such that G has an injective k-edge coloring.In this paper,we prove that x'i(G)≤9 if G is a planar graph with maximum degreeΔ≤4,girth g≥6 and without intersecting 6-cycles.展开更多
A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-dege...A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.展开更多
DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improve...DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].展开更多
We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices...We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.展开更多
A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))...A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.展开更多
Fuzzy graph theory is used for solving real-world problems in different fields, in- cluding theoretical computer science, engineering, physics, combinatorics and medical sciences. In this paper, we present conepts of ...Fuzzy graph theory is used for solving real-world problems in different fields, in- cluding theoretical computer science, engineering, physics, combinatorics and medical sciences. In this paper, we present conepts of bipolar neutrosophic multigraphs, bipolar neutrosophic planar graphs, bipolar neutrosophic dual graphs, and study some of their related properties. We also describe applications of bipolar neutrosophic graphs in road network and electrical connections.展开更多
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge c...An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a（G）.In this paper we prove that χ ’ a（G） ≤（G） ＋ 5 for planar graphs G without adjacent triangles.展开更多
Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a v...Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.展开更多
The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graph theory. In t...The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graph theory. In this paper, it was shown that the power domination number of an outerplanar graph with the diameter two or a 2-connected outerplanar graph with the diameter three is precisely one. Upper bounds on the power domination number for a general planar graph with the diameter two or three were determined as an immediate consequences of results proven by Dorfling, et al. Also, an infinite family of outerplanar graphs with the diameter four having arbitrarily large power domination numbers were given.展开更多
An(O_(k1),O_(k2))-partition of a graph G is the partition of V(G)into two non-empty subsets V_(1) and V2,such that G[V_(1)]and G[V_(2)]are graphs with components of order at most k_(1) and k_(2),respectively.In this p...An(O_(k1),O_(k2))-partition of a graph G is the partition of V(G)into two non-empty subsets V_(1) and V2,such that G[V_(1)]and G[V_(2)]are graphs with components of order at most k_(1) and k_(2),respectively.In this paper,we consider the problem of partitioning the vertex set of a planar graph with girth restriction such that each part induces a graph with components of bounded order.We prove that every planar graph with girth at least 6 and i-cycle is not intersecting with j-cycle admits an(O_(2),O_(3))-partition,where i∈[6,7,8]and j∈[6,7,8,9].展开更多
In this paper, it is shown that for every maximal planar graph G=(V,E) , a strong embedding on some non orientable surface with genus at most |V(G)|-22 is admitted such that the surface dual of G is also a...In this paper, it is shown that for every maximal planar graph G=(V,E) , a strong embedding on some non orientable surface with genus at most |V(G)|-22 is admitted such that the surface dual of G is also a planar graph. As a corollary, an interpolation theorem for strong embeddings of G on non orientable surfaces is obtained.展开更多
A graph G is called（k,d）＊-choosable if for every list assignment L satisfying ｜L（v）｜=k for all v ∈ V（G）,there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same co...A graph G is called（k,d）＊-choosable if for every list assignment L satisfying ｜L（v）｜=k for all v ∈ V（G）,there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself.In this paper,it is shown that every planar graph without 6-circuits and a triangle adjacent to itself or a quadrangle is（3,1）＊-choosable.展开更多
An equitable(O^(1)_(k),O^(2)_(k),...,O^(m)_(k))-partition of a graph G,which is also called a k cluster m-partition,is the partition of V(G)into m non-empty subsets V_(1),V_(2),...,Vm such that for every integer i in{...An equitable(O^(1)_(k),O^(2)_(k),...,O^(m)_(k))-partition of a graph G,which is also called a k cluster m-partition,is the partition of V(G)into m non-empty subsets V_(1),V_(2),...,Vm such that for every integer i in{1,2,...,m},G[Vi]is a graph with components of order at most k,and for each distinct pair i,j in{1,...,m},there is−1≤|Vi|−|Vj|≤1.In this paper,we proved that every planar graph G with minimum degreeδ(G)≥2 and girth g(G)≥12 admits an equitable(O_(1)^(7),O^(2)_(7),...,O^(m)_(7))-partition,for any integer m≥2.展开更多
A graph G is said to be planar if G can be drawn on the plane in such a way that its edges intersect only at their endpoints.In this paper,all the planar graphs without isolated vertices whose second largest eigenvalu...A graph G is said to be planar if G can be drawn on the plane in such a way that its edges intersect only at their endpoints.In this paper,all the planar graphs without isolated vertices whose second largest eigenvalue smaller than(√5-1)/2 are characterized.展开更多
The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove tha...The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.展开更多
A vertex coloring of a graph G is called a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors.Let G be a planar graph with girth at least five and maximum degree∆.We...A vertex coloring of a graph G is called a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors.Let G be a planar graph with girth at least five and maximum degree∆.We prove that G admits a 2-distance coloring with∆+4 colors when∆≥22,which improves a result of Dong and Lin(Discrete Appl.Math.217:495–505,2017).展开更多
A graph G is edge-k-choosable if,for any assignment of lists L(e)of at least k colors to all edges e∈E(G),there exists a proper edge coloring such that the color of e belongs to L(e)for all e∈E(G).One of Vizing’s c...A graph G is edge-k-choosable if,for any assignment of lists L(e)of at least k colors to all edges e∈E(G),there exists a proper edge coloring such that the color of e belongs to L(e)for all e∈E(G).One of Vizing’s classic conjectures asserts that every graph is edge-(Δ+1)-choosable.It is known since 1999 that this conjecture is true for general graphs withΔ≤4.More recently,in 2015,Bonamy confirmed the conjecture for planar graph withΔ≥8,but the conjecture is still open for planar graphs with 5≤Δ≤7.We confirm the conjecture for planar graphs withΔ≥6 in which every 7-cycle(if any)induces a C_(7)(so,without chords),thereby extending a result due to Dong,Liu and Li.展开更多
Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem ...Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem was improved to k≤7 by Borodin et al.However,by permitting the existence of adjacent triangles except K4,for an arbitrary integer k≥5,there exists a planar graph without cycles of length from 5 to k such that G is not 3-colorable.Let d denote the minimum distance between two diamonds in G,where a diamond is the union of two adjacent triangles.In this paper,we prove that a planar graph G with d≥2 and without cycles of length from 5 to 18 is 3-colorable.The reader is invited to find the smallest integer k such that a planar graph G with d≥2 and without cycles of length from 5 to k is 3-colorable.展开更多
The spectral radius is an important parameter of a graph related to networks. A method for estimating the spectral radius of each spanning subgraph is used to prove that the spectral radius of a Hamiltonian planar g...The spectral radius is an important parameter of a graph related to networks. A method for estimating the spectral radius of each spanning subgraph is used to prove that the spectral radius of a Hamiltonian planar graph of order n≥4 is less than or equal to 2+3n-11 and the spectral radius of the outerplanar graph of order n≥6 is less than or equal to 22+n-5, which are improvements over previous results. A direction for further study is then suggested.展开更多
This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial a...This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.12071265,12001481)the Natural Science Foundation of Shandong Province(Grant No.ZR2021MA103)the Youth Innovation Team Project of Shandong Province Universities(Grant No.2024KJG078).
文摘An injective k-edge coloring of a graph G is k-edge coloringκof G such thatκ(e1)≠κ(e3)for any three consecutive edges ei,e2 and e3 of a path or a triangle.The injective chromatic index of G,denoted by x'i(G),is the smallest integer k such that G has an injective k-edge coloring.In this paper,we prove that x'i(G)≤9 if G is a planar graph with maximum degreeΔ≤4,girth g≥6 and without intersecting 6-cycles.
文摘A graph G is called d-degenerate if every subgraph of G has a vertex of degree at most d.It was known that planar graphs are 5-degenerate and every planar graph without k-cycles for some prescribed k∈{3,5,6}is 3-degenerate.In this paper,we show that if G is a planar graph without kites and 9-or 10-cycles,then G is 3-degenerate,hence 4-choosable and list vertex 2-arborable.
基金Partially supported by NSFC(No.12301436)NSF of Guangxi Province(No.2025GXNSFAA069811)。
文摘DP-coloring as a generalization of list coloring was introduced recently by Dvo˘r´ak and Postle.In this paper,we show that planar graphs without 5-cycles adjacent to two triangles are DP-4-colorable,which improves the results of[Discrete Math.,2018,341(7):1983–1986]and[Discrete Appl.Math.,2020,277:245–251].
文摘We assign vertex v of G a list L(v)which L(v)∈2^(N)and N is the set of positive integers.A graph G is k-L(p,1)-choosable if G has a mappingφ:φ(v)2 L(v)which|L(v)|≥k for every v 2 V(G)such that for any two vertices u and w,|φ(u)-φ(w)|≥p when they are adjacent,and|φ(u)-φ(w)|≥1 when they are at distance 2.In this paper,we proved that:(1)for every planar graph with g(G)≥5 andΔ≥5,G is 12-L(1,1)-choosable.(2)for every planar graph with g(G)≥6 andΔ≥15,G is(Δ+6)-L(2,1)-choosable.
基金Supported by the National Natural Science Foundation of China(Grant No.12071265)the Natural Science Foundation of Shandong Province(Grant No.ZR2019MA032)。
文摘A list assignment of a graph G is a function L:V(G)∪E(G)→2^(N).A graph G is L-(2,1)-Total labeling if there exists a function c such that c(x)∈L(x)for all x∈V(G)∪E(G),|c(u)-c(v)|≥1 if uv∈E(G),|c(e_(1))-c(e_(2))|≥1 if the edges e_(1)and e_(2)are adjacent,and|c(u)-c(e)|≥2 if the vertex u is incident to the edge e.A graph G is k-(2,1)-Total choosable if G is L-(2,1)-Total labeling for every list assignment L provided that|L(x)|=k,x∈V(G)∪E(G).The(2,1)-Total choice number of G,denoted by C_(2,1)^T(G),is the minimum k such that G is k-(2,1)-Total choosable.In this paper,we prove that if G is a planar graph with△(G)≥11,then C_(2,1)^T(G)≤△+4.
文摘Fuzzy graph theory is used for solving real-world problems in different fields, in- cluding theoretical computer science, engineering, physics, combinatorics and medical sciences. In this paper, we present conepts of bipolar neutrosophic multigraphs, bipolar neutrosophic planar graphs, bipolar neutrosophic dual graphs, and study some of their related properties. We also describe applications of bipolar neutrosophic graphs in road network and electrical connections.
文摘An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a（G）.In this paper we prove that χ ’ a（G） ≤（G） ＋ 5 for planar graphs G without adjacent triangles.
基金The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through the Large Group Research Project under grant number(R.G.P.2/181/44).
文摘Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.
基金Project supporte（t by the National Natural Science Foundation of China （Grant No.10571117）, and the Youth Science Foundation of Shanghai Municipal Commission of Education （Grant No.01QN6262）
文摘The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graph theory. In this paper, it was shown that the power domination number of an outerplanar graph with the diameter two or a 2-connected outerplanar graph with the diameter three is precisely one. Upper bounds on the power domination number for a general planar graph with the diameter two or three were determined as an immediate consequences of results proven by Dorfling, et al. Also, an infinite family of outerplanar graphs with the diameter four having arbitrarily large power domination numbers were given.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1207126512271331)the Natural Science Foundation of Shandong Province(Grant No.ZR202102250232).
文摘An(O_(k1),O_(k2))-partition of a graph G is the partition of V(G)into two non-empty subsets V_(1) and V2,such that G[V_(1)]and G[V_(2)]are graphs with components of order at most k_(1) and k_(2),respectively.In this paper,we consider the problem of partitioning the vertex set of a planar graph with girth restriction such that each part induces a graph with components of bounded order.We prove that every planar graph with girth at least 6 and i-cycle is not intersecting with j-cycle admits an(O_(2),O_(3))-partition,where i∈[6,7,8]and j∈[6,7,8,9].
文摘In this paper, it is shown that for every maximal planar graph G=(V,E) , a strong embedding on some non orientable surface with genus at most |V(G)|-22 is admitted such that the surface dual of G is also a planar graph. As a corollary, an interpolation theorem for strong embeddings of G on non orientable surfaces is obtained.
基金Supported by the Natural Science Research Project of Ordinary Universities in Jiangsu(08KJB110002)Supported by the Program for ETHYTC(08QNZCK03)Supported by the NSFC(10671095)
文摘A graph G is called（k,d）＊-choosable if for every list assignment L satisfying ｜L（v）｜=k for all v ∈ V（G）,there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself.In this paper,it is shown that every planar graph without 6-circuits and a triangle adjacent to itself or a quadrangle is（3,1）＊-choosable.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1207126512271331)the Natural Science Foundation of Shandong Province(Grant No.ZR202102250232).
文摘An equitable(O^(1)_(k),O^(2)_(k),...,O^(m)_(k))-partition of a graph G,which is also called a k cluster m-partition,is the partition of V(G)into m non-empty subsets V_(1),V_(2),...,Vm such that for every integer i in{1,2,...,m},G[Vi]is a graph with components of order at most k,and for each distinct pair i,j in{1,...,m},there is−1≤|Vi|−|Vj|≤1.In this paper,we proved that every planar graph G with minimum degreeδ(G)≥2 and girth g(G)≥12 admits an equitable(O_(1)^(7),O^(2)_(7),...,O^(m)_(7))-partition,for any integer m≥2.
基金Supported by the National Natural Science Foundation of China(Grant No.12171154)。
文摘A graph G is said to be planar if G can be drawn on the plane in such a way that its edges intersect only at their endpoints.In this paper,all the planar graphs without isolated vertices whose second largest eigenvalue smaller than(√5-1)/2 are characterized.
文摘The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.
基金supported by TUBITAK(The Scientific and Technological Research Council of Türkiye)under the project number 122F250。
文摘A vertex coloring of a graph G is called a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors.Let G be a planar graph with girth at least five and maximum degree∆.We prove that G admits a 2-distance coloring with∆+4 colors when∆≥22,which improves a result of Dong and Lin(Discrete Appl.Math.217:495–505,2017).
基金Supported by NSFC(Grant Nos.12271438,12071370 and U1803263)China Scholarship Council(Grant No.202006290386)。
文摘A graph G is edge-k-choosable if,for any assignment of lists L(e)of at least k colors to all edges e∈E(G),there exists a proper edge coloring such that the color of e belongs to L(e)for all e∈E(G).One of Vizing’s classic conjectures asserts that every graph is edge-(Δ+1)-choosable.It is known since 1999 that this conjecture is true for general graphs withΔ≤4.More recently,in 2015,Bonamy confirmed the conjecture for planar graph withΔ≥8,but the conjecture is still open for planar graphs with 5≤Δ≤7.We confirm the conjecture for planar graphs withΔ≥6 in which every 7-cycle(if any)induces a C_(7)(so,without chords),thereby extending a result due to Dong,Liu and Li.
基金partially supported by National Nature Science Foundation of China(No 12361067)Nature Science Foundation of Guangxi(No.2024GXNSFAA010506)+1 种基金Guangxi college students’innovation and entrepreneurship project(S202410608013)School-level talent programs(2022KJQD04 and2023MDKJ001)
文摘Erdös raised the following problem according to Steinberg's conjecture:Is there an integer such that every planar graph without cycles of length from 4 to k is 3-colorable.By far,the result about the problem was improved to k≤7 by Borodin et al.However,by permitting the existence of adjacent triangles except K4,for an arbitrary integer k≥5,there exists a planar graph without cycles of length from 5 to k such that G is not 3-colorable.Let d denote the minimum distance between two diamonds in G,where a diamond is the union of two adjacent triangles.In this paper,we prove that a planar graph G with d≥2 and without cycles of length from 5 to 18 is 3-colorable.The reader is invited to find the smallest integer k such that a planar graph G with d≥2 and without cycles of length from 5 to k is 3-colorable.
基金the National Natural Science Foundationof China (No.196 710 5 0 )
文摘The spectral radius is an important parameter of a graph related to networks. A method for estimating the spectral radius of each spanning subgraph is used to prove that the spectral radius of a Hamiltonian planar graph of order n≥4 is less than or equal to 2+3n-11 and the spectral radius of the outerplanar graph of order n≥6 is less than or equal to 22+n-5, which are improvements over previous results. A direction for further study is then suggested.
文摘This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.
