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.展开更多
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 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 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.展开更多
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].展开更多
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 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.展开更多
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.展开更多
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.展开更多
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.展开更多
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 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.展开更多
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.展开更多
文摘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.
基金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.
文摘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.
文摘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.
基金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].
基金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.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.
基金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.
文摘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.
文摘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 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 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.
基金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.
