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