The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, t...The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.展开更多
A linear coloring of a graph G is a proper vertex coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc（G） of G is the sm...A linear coloring of a graph G is a proper vertex coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc（G） of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every planar graph G with maximum degree 5 is 11-linear-colorable.展开更多
The oriented diameter of an undirected graph G,denoted by diam(G^(→)),is defined as the minimum diameter of any strong orientation of G.In this paper,we prove that the oriented diameter of a bridgeless C_(4)-free gra...The oriented diameter of an undirected graph G,denoted by diam(G^(→)),is defined as the minimum diameter of any strong orientation of G.In this paper,we prove that the oriented diameter of a bridgeless C_(4)-free graph is at most(37n)/(δ^(2)-2[δ/2])+19.We also consider some upper bounds of in terms of girth g,minimum degree△and maximum degree and give some upper bounds of diam(G^(→))in bridgeless(C_(4),C_(5))-free graphs.展开更多
Delay aware routing is now widely used to provide efficient network transmission. However, for newly developing or developed mobile communication networks(MCN), only limited delay data can be obtained. In such a netwo...Delay aware routing is now widely used to provide efficient network transmission. However, for newly developing or developed mobile communication networks(MCN), only limited delay data can be obtained. In such a network, the delay is with epistemic uncertainty, which makes the traditional routing scheme based on deterministic theory or probability theory not applicable. Motivated by this problem, the MCN with epistemic uncertainty is first summarized as a dynamic uncertain network based on uncertainty theory, which is widely applied to model epistemic uncertainties. Then by modeling the uncertain end-toend delay, a new delay bounded routing scheme is proposed to find the path with the maximum belief degree that satisfies the delay threshold for the dynamic uncertain network. Finally, a lowEarth-orbit satellite communication network(LEO-SCN) is used as a case to verify the effectiveness of our routing scheme. It is first modeled as a dynamic uncertain network, and then the delay bounded paths with the maximum belief degree are computed and compared under different delay thresholds.展开更多
Flexural toppling occurs when a series of layered rock masses bend towards their free face.It is important to evaluate the maximum bending degree and the requirement of supports of flexural toppling rock mass to preve...Flexural toppling occurs when a series of layered rock masses bend towards their free face.It is important to evaluate the maximum bending degree and the requirement of supports of flexural toppling rock mass to prevent rock mass cracking and even failure leading to a landslide.Based on the rock tensile strain-softening model,this study proposes a method for calculating the maximum curvature(C_(ppmax))of flexural toppling rock masses.By applying this method to calculate Cppmax of 9 types of rock masses with different hardness and rock layer thickness,some conclusions are drawn:(1)the internal key factors affecting C_(ppmax)are E^(⋆)(E^(⋆)=E_(ss)/E_(0),where E_(0)and E_(ss)are the mean deformation moduli of the rock before and after reaching its peak tensile strength,respectively),the strainεt corresponding to the tensile strength of rock,and the thickness(h)of rock layers;(2)hard rock layers are more likely to develop into block toppling than soft rock layers;and(3)thin rock layers are more likely to remain in flexural toppling state than thick rock layers.In addition,it is found that C_(ppmax)for flexural toppling rock masses composed of bedded rocks such as gneiss is related to the tensile direction.展开更多
In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{...In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？展开更多
In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the disting...In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.展开更多
AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivi...AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivity C, then n≤c(d_k-d)/(d-1)M+d+1. It improves the previous knownresults, and it, in fact, is the best possible for several interesting cases. A similar result for arcconnectivity is also established.展开更多
Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is th...Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is the Total Coloring Conjecture,which asserts that every graph of maximum degreeΔadmits a(Δ+2)-total-coloring.More precisely,this conjecture has been verified forΔ≤5,and it is still open whenΔ=6,even for planar graphs.Let mad(G)denote the maximum average degree of the graph G.In this paper,we prove that every graph G withΔ(G)=6 and mad(G)<23/5 admits an 8-total-coloring.展开更多
A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>...A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>: <em>E</em>(<em>G</em>) → {1, 2, …, <em>k</em>} such that no two adjacent edges receive the same color. A neighbor sum distinguishing <em>k</em>-edge coloring of <em>G</em> is a proper <em>k</em>-edge coloring of <em>G</em> such that <img src="Edit_28f0a24c-7d3f-4bdc-b58c-46dfa2add4b4.bmp" alt="" /> for each edge <em>uv</em> ∈ <em>E</em>(<em>G</em>). The neighbor sum distinguishing index of a graph <em>G</em> is the least integer <em>k</em> such that <em>G </em>has such a coloring, denoted by <em>χ’</em><sub>Σ</sub>(<em>G</em>). Let <img src="Edit_7525056f-b99d-4e38-b940-618d16c061e2.bmp" alt="" /> be the maximum average degree of <em>G</em>. In this paper, we prove <em>χ</em>’<sub>Σ</sub>(<em>G</em>) ≤ max{9, Δ(<em>G</em>) +1} for any normal graph <em>G</em> with <img src="Edit_e28e38d5-9b6d-46da-bfce-2aae47cc36f3.bmp" alt="" />. Our approach is based on the discharging method and Combinatorial Nullstellensatz.展开更多
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.展开更多
In the practice of control the industrial processes, proportional-integral-derivative controller remains pivotal due to its simple structure and system performance-oriented tuning process. In this paper are presented ...In the practice of control the industrial processes, proportional-integral-derivative controller remains pivotal due to its simple structure and system performance-oriented tuning process. In this paper are presented two approaches for synthesis the proportional-integral-derivative controller to the models of objects with inertia, that offer the procedure of system performance optimization based on maximum stability degree criterion. The proposed algorithms of system performance optimization were elaborated for model of objects with inertia second and third order and offer simple analytical expressions for tuning the PID controller. Validation and verification are conducted through computer simulations using MATLAB, demonstrating successful performance optimization and showcasing the effectiveness PID controllers’ tuning. The proposed approaches contribute insights to the field of control, offering a pathway for optimizing the performance of second and third-order inertial systems through robust controller synthesis.展开更多
For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [...For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [ci - cj] ≤1 for any two colors i and j, then c is an equitable edge coloring of G. The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring. The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G. In this paper, we determine the equitable adjacent strong chromatic index of the joins of paths and cycles. Precisely, we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.展开更多
In this paper we consider the random r-uniform r-partite hypergraph model H（n1, n2,…, nr; n, p） which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where ｜Vi｜ = ni = ni...In this paper we consider the random r-uniform r-partite hypergraph model H（n1, n2,…, nr; n, p） which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where ｜Vi｜ = ni = ni（n） （1 ≤ i ≤ r） are positive integer-valued functions on n with n1 ＋n2 ＋… ＋nr =n, and each r-subset containing exactly one element in Vi （1 ≤ i ≤ r） is chosen to be a hyperedge of Hp ∈H（n1,n2,…,nr;n,p） with probability p = p（n）, all choices being independent. Let △V1 = △V1 （H） and δv1 = δv1（H） be the maximum and minimum degree of vertices in V1 of H, respectively; Xd,V1 = Xd,V1 （H）, Yd,V1 = Yd,V1 （H）, Zd,V1 = Zd,V1 （H） and Zc,d,V1=Zc,d,V1 （H） be the number of vertices in V1 of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H（n1, n2,…, nr; n,p）, Xd,V1, Yd,V1, Zd,V1, and Zc,d,V1all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D（n） such that in the space H（n1, n2,…,nr; n, p）, lim n→＋∞ P（△v1 = D（n）） = 1？ What is the range of p such that a.e., Hp ∈ H（n1,n2,...,nr;n,p） has a unique vertex in V1 with degree Av1（Hp）？ Both answers are p = o（logn1/N）, where N = r ∏ i=2 ni. The corresponding problems on δv1（Hp） also are considered, and we obtained the answers are p ≤ （1＋o（1））（logn1/N） andp=o （log n1/N）, respectively.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
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.展开更多
Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent ...Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent edges receive the same color. An Ⅰ-total coloring of a graph G is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, we have C_φ(u) = C_φ(v), where C_φ(u) denotes the set of colors of u and its incident edges. The minimum number of colors required for an adjacent vertex distinguishing Ⅰ-total coloring of G is called the adjacent vertex distinguishing Ⅰ-total chromatic number, denoted by χ_at^i(G).In this paper, we characterize the adjacent vertex distinguishing Ⅰ-total chromatic number of outerplanar graphs.展开更多
Let G be a graph and let its maxiraum degree and maximum average degree be denoted by △（G） and mad（G）, respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph ...Let G be a graph and let its maxiraum degree and maximum average degree be denoted by △（G） and mad（G）, respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E（G）, the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by X∑ （G）. Flandrin et al. proposed the following conjecture that X＇∑ （G） ≤△ （G） ＋ 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad（G） 〈 37/12and △ （G）≥ 7.展开更多
基金This research is supported by NNSF of China(40301037, 10471131)
文摘The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.
基金Supported by the National Natural Science Foundation of China (Grant No. 11071223)the Natural ScienceFoundation of Zhejiang Province (Grant No. Z6090150)Research Project of Zhejiang Educational Committee(Grant No. Y201121311)
文摘A linear coloring of a graph G is a proper vertex coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc（G） of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every planar graph G with maximum degree 5 is 11-linear-colorable.
基金supported by the Natural Science Foundation of Xinjiang(No.2020D04046)the Natio Natural Science Foundation of China(No.12061073).
文摘The oriented diameter of an undirected graph G,denoted by diam(G^(→)),is defined as the minimum diameter of any strong orientation of G.In this paper,we prove that the oriented diameter of a bridgeless C_(4)-free graph is at most(37n)/(δ^(2)-2[δ/2])+19.We also consider some upper bounds of in terms of girth g,minimum degree△and maximum degree and give some upper bounds of diam(G^(→))in bridgeless(C_(4),C_(5))-free graphs.
基金National Natural Science Foundation of China (61773044,62073009)National key Laboratory of Science and Technology on Reliability and Environmental Engineering(WDZC2019601A301)。
文摘Delay aware routing is now widely used to provide efficient network transmission. However, for newly developing or developed mobile communication networks(MCN), only limited delay data can be obtained. In such a network, the delay is with epistemic uncertainty, which makes the traditional routing scheme based on deterministic theory or probability theory not applicable. Motivated by this problem, the MCN with epistemic uncertainty is first summarized as a dynamic uncertain network based on uncertainty theory, which is widely applied to model epistemic uncertainties. Then by modeling the uncertain end-toend delay, a new delay bounded routing scheme is proposed to find the path with the maximum belief degree that satisfies the delay threshold for the dynamic uncertain network. Finally, a lowEarth-orbit satellite communication network(LEO-SCN) is used as a case to verify the effectiveness of our routing scheme. It is first modeled as a dynamic uncertain network, and then the delay bounded paths with the maximum belief degree are computed and compared under different delay thresholds.
基金funded by the National Natural Science Foundation of China(No.41972264)Zhejiang Provincial Natural Science Foundation of China(No.LR22E080002)the Key R&D Project of Zhejiang Province(No.2021C03159).
文摘Flexural toppling occurs when a series of layered rock masses bend towards their free face.It is important to evaluate the maximum bending degree and the requirement of supports of flexural toppling rock mass to prevent rock mass cracking and even failure leading to a landslide.Based on the rock tensile strain-softening model,this study proposes a method for calculating the maximum curvature(C_(ppmax))of flexural toppling rock masses.By applying this method to calculate Cppmax of 9 types of rock masses with different hardness and rock layer thickness,some conclusions are drawn:(1)the internal key factors affecting C_(ppmax)are E^(⋆)(E^(⋆)=E_(ss)/E_(0),where E_(0)and E_(ss)are the mean deformation moduli of the rock before and after reaching its peak tensile strength,respectively),the strainεt corresponding to the tensile strength of rock,and the thickness(h)of rock layers;(2)hard rock layers are more likely to develop into block toppling than soft rock layers;and(3)thin rock layers are more likely to remain in flexural toppling state than thick rock layers.In addition,it is found that C_(ppmax)for flexural toppling rock masses composed of bedded rocks such as gneiss is related to the tensile direction.
文摘In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？
文摘In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.
基金This project is supported by the National Natural Science Foundation of China
文摘AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivity C, then n≤c(d_k-d)/(d-1)M+d+1. It improves the previous knownresults, and it, in fact, is the best possible for several interesting cases. A similar result for arcconnectivity is also established.
基金This work was supported by the National Natural Science Foundation of China(11471193,11631014)the Foundation for Distinguished Young Scholars of Shandong Province(JQ201501)the Fundamental Research Funds of Shandong University and Independent Innovation Foundation of Shandong University(IFYT14012).
文摘Given a graph G=(V,E)and a positive integer k,a k-total-coloring of G is a mappingφ:V⋃E→{1,2,⋯,k}such that no two adjacent or incident elements receive the same color.The central problem of the total-colorings is the Total Coloring Conjecture,which asserts that every graph of maximum degreeΔadmits a(Δ+2)-total-coloring.More precisely,this conjecture has been verified forΔ≤5,and it is still open whenΔ=6,even for planar graphs.Let mad(G)denote the maximum average degree of the graph G.In this paper,we prove that every graph G withΔ(G)=6 and mad(G)<23/5 admits an 8-total-coloring.
文摘A proper <em>k</em>-edge coloring of a graph <em>G</em> = (<em>V</em>(<em>G</em>), <em>E</em>(<em>G</em>)) is an assignment <em>c</em>: <em>E</em>(<em>G</em>) → {1, 2, …, <em>k</em>} such that no two adjacent edges receive the same color. A neighbor sum distinguishing <em>k</em>-edge coloring of <em>G</em> is a proper <em>k</em>-edge coloring of <em>G</em> such that <img src="Edit_28f0a24c-7d3f-4bdc-b58c-46dfa2add4b4.bmp" alt="" /> for each edge <em>uv</em> ∈ <em>E</em>(<em>G</em>). The neighbor sum distinguishing index of a graph <em>G</em> is the least integer <em>k</em> such that <em>G </em>has such a coloring, denoted by <em>χ’</em><sub>Σ</sub>(<em>G</em>). Let <img src="Edit_7525056f-b99d-4e38-b940-618d16c061e2.bmp" alt="" /> be the maximum average degree of <em>G</em>. In this paper, we prove <em>χ</em>’<sub>Σ</sub>(<em>G</em>) ≤ max{9, Δ(<em>G</em>) +1} for any normal graph <em>G</em> with <img src="Edit_e28e38d5-9b6d-46da-bfce-2aae47cc36f3.bmp" alt="" />. Our approach is based on the discharging method and Combinatorial Nullstellensatz.
文摘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.
文摘In the practice of control the industrial processes, proportional-integral-derivative controller remains pivotal due to its simple structure and system performance-oriented tuning process. In this paper are presented two approaches for synthesis the proportional-integral-derivative controller to the models of objects with inertia, that offer the procedure of system performance optimization based on maximum stability degree criterion. The proposed algorithms of system performance optimization were elaborated for model of objects with inertia second and third order and offer simple analytical expressions for tuning the PID controller. Validation and verification are conducted through computer simulations using MATLAB, demonstrating successful performance optimization and showcasing the effectiveness PID controllers’ tuning. The proposed approaches contribute insights to the field of control, offering a pathway for optimizing the performance of second and third-order inertial systems through robust controller synthesis.
基金Supported by the Fundamental Research Funds for the Central Universities(Grant Nos. 2011B019)the National Natural Science Foundation of China (Grant Nos. 10971144+2 种基金1110102011171026)the Natural Science Foundation of Beijing (Grant No. 1102015)
文摘For a proper edge coloring c of a graph G, if the sets of colors of adjacent vertices are distinct, the edge coloring c is called an adjacent strong edge coloring of G. Let ci be the number of edges colored by i. If [ci - cj] ≤1 for any two colors i and j, then c is an equitable edge coloring of G. The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring. The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G. In this paper, we determine the equitable adjacent strong chromatic index of the joins of paths and cycles. Precisely, we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.
基金Supported in part by the National Natural Science Foundation of China under Grant No.11401102,11271307 and 11101086Fuzhou university of Science and Technology Development Fund No.2014-XQ-29
文摘In this paper we consider the random r-uniform r-partite hypergraph model H（n1, n2,…, nr; n, p） which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where ｜Vi｜ = ni = ni（n） （1 ≤ i ≤ r） are positive integer-valued functions on n with n1 ＋n2 ＋… ＋nr =n, and each r-subset containing exactly one element in Vi （1 ≤ i ≤ r） is chosen to be a hyperedge of Hp ∈H（n1,n2,…,nr;n,p） with probability p = p（n）, all choices being independent. Let △V1 = △V1 （H） and δv1 = δv1（H） be the maximum and minimum degree of vertices in V1 of H, respectively; Xd,V1 = Xd,V1 （H）, Yd,V1 = Yd,V1 （H）, Zd,V1 = Zd,V1 （H） and Zc,d,V1=Zc,d,V1 （H） be the number of vertices in V1 of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H（n1, n2,…, nr; n,p）, Xd,V1, Yd,V1, Zd,V1, and Zc,d,V1all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D（n） such that in the space H（n1, n2,…,nr; n, p）, lim n→＋∞ P（△v1 = D（n）） = 1？ What is the range of p such that a.e., Hp ∈ H（n1,n2,...,nr;n,p） has a unique vertex in V1 with degree Av1（Hp）？ Both answers are p = o（logn1/N）, where N = r ∏ i=2 ni. The corresponding problems on δv1（Hp） also are considered, and we obtained the answers are p ≤ （1＋o（1））（logn1/N） andp=o （log n1/N）, respectively.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
文摘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.
基金Supported by the National Natural Science Foundation of China(61163037,61163054,61363060)
文摘Let G be a simple graph with no isolated edge. An Ⅰ-total coloring of a graph G is a mapping φ : V(G) ∪ E(G) → {1, 2, · · ·, k} such that no adjacent vertices receive the same color and no adjacent edges receive the same color. An Ⅰ-total coloring of a graph G is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u and v of G, we have C_φ(u) = C_φ(v), where C_φ(u) denotes the set of colors of u and its incident edges. The minimum number of colors required for an adjacent vertex distinguishing Ⅰ-total coloring of G is called the adjacent vertex distinguishing Ⅰ-total chromatic number, denoted by χ_at^i(G).In this paper, we characterize the adjacent vertex distinguishing Ⅰ-total chromatic number of outerplanar graphs.
基金supported by the National Natural Science Foundation of China(Grant No.11571258)the National Natural Science Foundation of Shandong Province(Grant No.ZR2016AM01)Scientific Research Foundation of University of Jinan(Grant Nos.XKY1414 and XKY1613)
文摘Let G be a graph and let its maxiraum degree and maximum average degree be denoted by △（G） and mad（G）, respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E（G）, the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by X∑ （G）. Flandrin et al. proposed the following conjecture that X＇∑ （G） ≤△ （G） ＋ 2 for any connected graph with at least 3 vertices and G ≠ C5. In this paper, we prove that the conjecture holds for a normal graph with mad（G） 〈 37/12and △ （G）≥ 7.
