Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper...Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.展开更多
Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices o...Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.展开更多
L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the...L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the join graph on two fans is?λ(G) ≤ 2Δ+3.展开更多
Catalan number is an important class of combinatorial numbers. The maximal outerplanar graphs are important in graph theory. In this paper some formulas to enumerate the numbers of maximal outerplanar graphs by means ...Catalan number is an important class of combinatorial numbers. The maximal outerplanar graphs are important in graph theory. In this paper some formulas to enumerate the numbers of maximal outerplanar graphs by means of the compressing graph and group theory method are given first. Then the relationships between Catalan numbers and the numbers of labeled and unlabeled maximal outerplanar graphs are presented. The computed results verified these formulas.展开更多
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.展开更多
An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is ...An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is the sum of its label and the labels of its two end vertices. This concept was introduce by Brandt et al. They defined Xt＇（G） to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question： Is there a constant K with X^t（G） ≤△（G）＋1/2 K for all graphs G of maximum degree A（G）？ In this paper, we give a positive answer for outerplanar graphs ≤△（G）＋1/2 by showing that X＇t（G） ≤△（G）＋1/2 for each outerplanar graph G with maximum degree A（G）.展开更多
Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following resu...Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.展开更多
Let G be a planar graph without cut vertex, let X_c(G) be the vertex, edge, face-complete chromatic number of G and let p=|V(G)|. This paper proves X_c(G)=Δ(G)+1 if G is an outerplanar graph with Δ(G)≥7, or a high ...Let G be a planar graph without cut vertex, let X_c(G) be the vertex, edge, face-complete chromatic number of G and let p=|V(G)|. This paper proves X_c(G)=Δ(G)+1 if G is an outerplanar graph with Δ(G)≥7, or a high degree planar graph with p≥9 and Δ(G)≥p-2 or a maximal planar graph with Δ(G)≥14.展开更多
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.展开更多
A recently discovered approach including de Brujin graphs and Eulerian circuits are used to DNA sequencing and fragment assembly, and to simplify DNA graphs through a series of transformations on graphs and digraphs i...A recently discovered approach including de Brujin graphs and Eulerian circuits are used to DNA sequencing and fragment assembly, and to simplify DNA graphs through a series of transformations on graphs and digraphs in the field of bioinformatics. Since numbered graphs provide underlying mathematical models in studying the wide variety of seemingly unrelated practical applications, so graph colorings often are used to divide large systems into subsystems. A new graph labeling has been introduced and investigated.展开更多
Some kinds of the self-similar sets with overlapping structures are studied by introducing the graph-directed constructions satisfying the open set condition that coincide with these sets. In this way, the dimensions ...Some kinds of the self-similar sets with overlapping structures are studied by introducing the graph-directed constructions satisfying the open set condition that coincide with these sets. In this way, the dimensions and the measures are obtained.展开更多
文摘Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.
基金Project supported by the Vatural SCience Foundation of LNEC.
文摘Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.
文摘L(2,1)-labeling number of the product and the join graph on two fans are discussed in this paper, we proved that L(2,1)-labeling number of the product graph on two fans is?λ(G) ≤ Δ+3 , L(2,1)-labeling number of the join graph on two fans is?λ(G) ≤ 2Δ+3.
文摘Catalan number is an important class of combinatorial numbers. The maximal outerplanar graphs are important in graph theory. In this paper some formulas to enumerate the numbers of maximal outerplanar graphs by means of the compressing graph and group theory method are given first. Then the relationships between Catalan numbers and the numbers of labeled and unlabeled maximal outerplanar graphs are presented. The computed results verified these formulas.
基金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.
基金Supported by National Natural Science Foundation of China(Grant Nos.61070230 and 11101243)Doctoral Fund of Ministry of Education of China(Grant No.20100131120017)the Scientific Research Foundation for the Excellent Middle-Aged and Young Scientists of Shandong Province(Grant No.BS2012SF016)
文摘An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is the sum of its label and the labels of its two end vertices. This concept was introduce by Brandt et al. They defined Xt＇（G） to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question： Is there a constant K with X^t（G） ≤△（G）＋1/2 K for all graphs G of maximum degree A（G）？ In this paper, we give a positive answer for outerplanar graphs ≤△（G）＋1/2 by showing that X＇t（G） ≤△（G）＋1/2 for each outerplanar graph G with maximum degree A（G）.
基金Supported by the National Natural Science Foundation of China(No.10771197)
文摘Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.
基金Project supported by the Natural Science Foundation of the Railway Ministry and Gansu Province.
文摘Let G be a planar graph without cut vertex, let X_c(G) be the vertex, edge, face-complete chromatic number of G and let p=|V(G)|. This paper proves X_c(G)=Δ(G)+1 if G is an outerplanar graph with Δ(G)≥7, or a high degree planar graph with p≥9 and Δ(G)≥p-2 or a maximal planar graph with Δ(G)≥14.
基金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.
文摘A recently discovered approach including de Brujin graphs and Eulerian circuits are used to DNA sequencing and fragment assembly, and to simplify DNA graphs through a series of transformations on graphs and digraphs in the field of bioinformatics. Since numbered graphs provide underlying mathematical models in studying the wide variety of seemingly unrelated practical applications, so graph colorings often are used to divide large systems into subsystems. A new graph labeling has been introduced and investigated.
基金Project supported by the National Natural Science Foundation of China and Mathematics Center ofMorningside, Chinese Academy Sc
文摘Some kinds of the self-similar sets with overlapping structures are studied by introducing the graph-directed constructions satisfying the open set condition that coincide with these sets. In this way, the dimensions and the measures are obtained.
