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.展开更多
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.展开更多
The relationship between a link diagram and its corresponding planar graph is briefly reviewed. A necessary and sufficient condition is given to detect when a planar graph corresponds to a knot. The relationship betwe...The relationship between a link diagram and its corresponding planar graph is briefly reviewed. A necessary and sufficient condition is given to detect when a planar graph corresponds to a knot. The relationship between planar graph and almost planar Seifert surface is discussed. Using planar graph, we construct an alternating amphicheiral prime knot with crossing number n for any even number n 〉 4. This gives an affirmative answer to problem 1.66(B) on Kirby's problem list .展开更多
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.展开更多
The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that ...The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.展开更多
A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge.It is known that every outer-1-planar graph is a planar partial3-tree...A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge.It is known that every outer-1-planar graph is a planar partial3-tree.In this paper,we conjecture that every planar graph G has a proper incidence(Δ(G)+2)-coloring and confirm it for outer-1-planar graphs with maximum degree at least 8 or with girth at least 4.Specifically,we prove that every outer-1-planar graph G has an incidence(Δ(G)+3,2)-coloring,and every outer-1-planar graph G with maximum degree at least 8 or with girth at least 4 has an incidence(Δ(G)+2,2)-coloring.展开更多
图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的...图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的每张平面图是,这被显示出(3,1 )*-choosable。展开更多
A neighbor sum distinguishing(NSD)total coloringφof G is a proper total coloring of G such thatΣz∈EG(u)U{u}φ(z)≠Σz∈EG(v)U{v}φ(z)for each edge uv∈E(G),where EG(u)is the set of edges incident with a vertex u.In...A neighbor sum distinguishing(NSD)total coloringφof G is a proper total coloring of G such thatΣz∈EG(u)U{u}φ(z)≠Σz∈EG(v)U{v}φ(z)for each edge uv∈E(G),where EG(u)is the set of edges incident with a vertex u.In 2015,Pilśniak and Wozniak conjectured that every graph with maximum degreeΔhas an NSD total(Δ+3)-coloring.Recently,Yang et al.proved that the conjecture holds for planar graphs withΔ≥10,and Qu et al.proved that the list version of the conjecture also holds for planar graphs withΔ≥13.In this paper,we improve their results and prove that the list version of the conjecture holds for planar graphs withΔ≥10.展开更多
A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism t...A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism to the odd cycle Cp).The assumption of p≥5 being prime number is necessary,and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p-2 is Cp-colorable for prime p≥5.In this paper,combining our previous results,we show the fractional coloring version of this conjecture is true.Particularly,the p=5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.展开更多
A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective ch...A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.展开更多
An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we ...An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.展开更多
Let G = (V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function (SCDF) of G if ∑e∈E(C) f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination numbe...Let G = (V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function (SCDF) of G if ∑e∈E(C) f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc(G) = min{∑e∈E f(e)| f is an SCDF of G}. This paper will characterize all maxima] planar graphs G with order n ≥ 6 and γ′sc(G) =n.展开更多
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.展开更多
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is (A + 1)-edge-choosable and...A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is (A + 1)-edge-choosable and (△ + 2)- total-choosable if △ ≥ 16, and is A-edge-choosable and (△ + 1)-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.展开更多
Pilsniak and Wozniak put forward the concept of neighbor sum distinguishing(NSD)total coloring and conjectured that any graph with maximum degreeΔadmits an NSD total(Δ+3)-coloring in 2015.In 2016,Qu et al.showed tha...Pilsniak and Wozniak put forward the concept of neighbor sum distinguishing(NSD)total coloring and conjectured that any graph with maximum degreeΔadmits an NSD total(Δ+3)-coloring in 2015.In 2016,Qu et al.showed that the list version of the conjecture holds for any planar graph withΔ≥13.In this paper,we prove that any planar graph withΔ≥7 but without 6-cycles satisfies the list version of the conjecture.展开更多
In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group (△ (G)+1)-edge-choosable, and some planar graphs with large girth and maximum degree are group △(...In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group (△ (G)+1)-edge-choosable, and some planar graphs with large girth and maximum degree are group △(G)-edge-choosable.展开更多
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V (K1 ∪ K2...A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V (K1 ∪ K2) with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V (K1∪K2) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.展开更多
文摘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.
基金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.
文摘The relationship between a link diagram and its corresponding planar graph is briefly reviewed. A necessary and sufficient condition is given to detect when a planar graph corresponds to a knot. The relationship between planar graph and almost planar Seifert surface is discussed. Using planar graph, we construct an alternating amphicheiral prime knot with crossing number n for any even number n 〉 4. This gives an affirmative answer to problem 1.66(B) on Kirby's problem list .
文摘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.
文摘The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.
基金Supported in part by the Natural Science Basic Research Program of Shaanxi(Nos.2023-JC-YB-001,2023-JC-YB-054)the Fundamental Research Funds for the Central Universities(No.ZYTS24076)the National Natural Science Foundation of China(No.11871055)。
文摘A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge.It is known that every outer-1-planar graph is a planar partial3-tree.In this paper,we conjecture that every planar graph G has a proper incidence(Δ(G)+2)-coloring and confirm it for outer-1-planar graphs with maximum degree at least 8 or with girth at least 4.Specifically,we prove that every outer-1-planar graph G has an incidence(Δ(G)+3,2)-coloring,and every outer-1-planar graph G with maximum degree at least 8 or with girth at least 4 has an incidence(Δ(G)+2,2)-coloring.
基金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)
文摘图 G 被叫(k, d )*-choosable 如果为为所有 v V (G) 的每表任务 L 令人满意的 | L (v)|=k,有 G 的 L 着色以便 G 的每个顶点至多有与象自己的一样的颜色有颜色的 d 邻居。在这份报纸,没有 6 电路和邻近自己或四角形的一个三角形的每张平面图是,这被显示出(3,1 )*-choosable。
基金supported by the National Natural Science Foundation of China (No.12271438, No.12071370 and U1803263)the Science Found of Qinhai Province (No.2022-ZJ-753)+2 种基金Shaanxi Fundamental Science Research Project for Mathematics and Physics (No.22JSZ009)Shangluo University Doctoral Initiation Fund Project(No.22SKY112)Shangluo University Key Disciplines Project (Discipline name:Mathematics)。
文摘A neighbor sum distinguishing(NSD)total coloringφof G is a proper total coloring of G such thatΣz∈EG(u)U{u}φ(z)≠Σz∈EG(v)U{v}φ(z)for each edge uv∈E(G),where EG(u)is the set of edges incident with a vertex u.In 2015,Pilśniak and Wozniak conjectured that every graph with maximum degreeΔhas an NSD total(Δ+3)-coloring.Recently,Yang et al.proved that the conjecture holds for planar graphs withΔ≥10,and Qu et al.proved that the list version of the conjecture also holds for planar graphs withΔ≥13.In this paper,we improve their results and prove that the list version of the conjecture holds for planar graphs withΔ≥10.
基金partially supported by the National Natural Science Foundation of China(Grant No.11971196)Hubei Provincial Science and Technology Innovation Base(Platform)Special Project 2020DFH002+1 种基金the second author was partially supported by the National Natural Science Foundation of China(Grant Nos.11901318,12131013)the Young Elite Scientists Sponsorship Program by Tianjin(Grant No.TJSQNTJ-2020-09)。
文摘A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism to the odd cycle Cp).The assumption of p≥5 being prime number is necessary,and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p-2 is Cp-colorable for prime p≥5.In this paper,combining our previous results,we show the fractional coloring version of this conjecture is true.Particularly,the p=5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.
基金supported by the National Natural Science Foundation of China (No.11871377)。
文摘A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.
基金the National Natural Science Foundation of China(Nos.11922112 and 11771221)the Natural Science Foundation of Tianjin(Nos.20JCZDJC00840 and 20JCJQJC00090)+2 种基金Yong-Xin Lan was partially supported by the National Natural Science Foundation of China(No.12001154)the Natural Science Foundation of Hebei Province(No.A2021202025)the Special Funds for Jointly Building Universities of Tianjin(No.280000307).
文摘An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.
基金Supported by Doctoral Scientific Research Fund of Harbin Normal University(Grant No.KGB201008)
文摘Let G = (V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function (SCDF) of G if ∑e∈E(C) f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc(G) = min{∑e∈E f(e)| f is an SCDF of G}. This paper will characterize all maxima] planar graphs G with order n ≥ 6 and γ′sc(G) =n.
基金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.
文摘A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree △ is (A + 1)-edge-choosable and (△ + 2)- total-choosable if △ ≥ 16, and is A-edge-choosable and (△ + 1)-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.
基金Supported by National Natural Science Foundation of China(Grant Nos.11871397,11671320 and U1803263)the Fundamental Research Funds for the Central Universities(Grant No.3102019ghjd003)+1 种基金the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2020JM-083)Shangluo University Key Disciplines Project(Discipline name Mathematics)。
文摘Pilsniak and Wozniak put forward the concept of neighbor sum distinguishing(NSD)total coloring and conjectured that any graph with maximum degreeΔadmits an NSD total(Δ+3)-coloring in 2015.In 2016,Qu et al.showed that the list version of the conjecture holds for any planar graph withΔ≥13.In this paper,we prove that any planar graph withΔ≥7 but without 6-cycles satisfies the list version of the conjecture.
基金Supported by the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2013JQ1002)the Fundamental Research Funds for the Central Universities(Grant No.K5051370003)National Natural Science Foundation of China(Grant Nos.11101243,11201440,11301410 and 61070230)
文摘In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group (△ (G)+1)-edge-choosable, and some planar graphs with large girth and maximum degree are group △(G)-edge-choosable.
基金Supported by National Natural Science Foundation of China (Grant Nos. 10971121, 11026184, 61070230)Research Fund for the Doctoral Program of Higher Education (Grant No. 20100131120017)+1 种基金Graduate Independent Innovation Foundation of Shandong University (Grant No. yzc10040)the financial support from the Chinese Ministry of Education Prize for Academic Doctoral Fellows
文摘A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2 V (K1 ∪ K2) with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1 V (K1∪K2) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.