In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has...In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has at most O（N5） many shortest cycles; If the shortest cycle of G is odd cycle, then G has at most O（N3） many shortest cycles; If G has been embedded in a surface 8g （Ng, g is a constant）, then it has at most O（N3） shortest cycles, moreover, if the shortest cycle of G is odd cycle, then, G has at most O（N2） many shortest cycles. We can find a cycle base of G, the number of odd cycles of G, the number of even cycles of G, the number of contractible cycles of G, the number of non-contractible cycles of G, are all decided. If the ∏-embedded graph G has ∏-twosided cycles, then, C contains a shortest ∏-twosided cycle of G, there is a polynomially bounded algorithm that finds a shortest ∏-twosided cycle of a ∏-embedded graph G, the new and simple solutions about the open problem of Bojan Mohar and Carsten Thomassen are obtained.展开更多
In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that ev...In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph without i-circuits for 4 ≤ i ≤ 11 - 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.展开更多
Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G ...Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G is of Class 1.展开更多
One paper in a preceding issue of this journal has introduced the Bayesian Ying-Yang(BYY)harmony learning from a perspective of problem solving,parameter learning,and model selection.In a complementary role,the paper ...One paper in a preceding issue of this journal has introduced the Bayesian Ying-Yang(BYY)harmony learning from a perspective of problem solving,parameter learning,and model selection.In a complementary role,the paper provides further insights from another perspective that a co-dimensional matrix pair(shortly co-dim matrix pair)forms a building unit and a hierarchy of such building units sets up the BYY system.The BYY harmony learning is re-examined via exploring the nature of a co-dim matrix pair,which leads to improved learning performance with refined model selection criteria and a modified mechanism that coordinates automatic model selection and sparse learning.Besides updating typical algorithms of factor analysis(FA),binary FA(BFA),binary matrix factorization(BMF),and nonnegative matrix factorization(NMF)to share such a mechanism,we are also led to(a)a new parametrization that embeds a de-noise nature to Gaussian mixture and local FA(LFA);(b)an alternative formulation of graph Laplacian based linear manifold learning;(c)a codecomposition of data and covariance for learning regularization and data integration;and(d)a co-dim matrix pair based generalization of temporal FA and state space model.Moreover,with help of a co-dim matrix pair in Hadamard product,we are led to a semi-supervised formation for regression analysis and a semi-blind learning formation for temporal FA and state space model.Furthermore,we address that these advances provide with new tools for network biology studies,including learning transcriptional regulatory,Protein-Protein Interaction network alignment,and network integration.展开更多
基金Supported in part by the National Natural Science Foundation of China under Grant No.10771225 and11171114the scientific research projects of state ethnic affairs commission(14ZYZ016)
文摘In this paper, the cycle＇s structure of embedded graphs in surfaces are studied. According to the method of fundamental cycles, the set C （C contains all shortest） is found. A undirected graph G with n vertices has at most O（N5） many shortest cycles; If the shortest cycle of G is odd cycle, then G has at most O（N3） many shortest cycles; If G has been embedded in a surface 8g （Ng, g is a constant）, then it has at most O（N3） shortest cycles, moreover, if the shortest cycle of G is odd cycle, then, G has at most O（N2） many shortest cycles. We can find a cycle base of G, the number of odd cycles of G, the number of even cycles of G, the number of contractible cycles of G, the number of non-contractible cycles of G, are all decided. If the ∏-embedded graph G has ∏-twosided cycles, then, C contains a shortest ∏-twosided cycle of G, there is a polynomially bounded algorithm that finds a shortest ∏-twosided cycle of a ∏-embedded graph G, the new and simple solutions about the open problem of Bojan Mohar and Carsten Thomassen are obtained.
文摘In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph without i-circuits for 4 ≤ i ≤ 11 - 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.
基金supported by Scientific Research Common Program of Beijing Municipal Commission of Education(No.KM201410011006)the Research Foundation for Youth Scholars of BTBU(No.QNJJ201226)BNSF(No.1132002,No.1122013)
基金Supported by the National Natural Science Foundation of China(No.11671053)
文摘Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G is of Class 1.
基金supported by the General Research Fund from Research Grant Council of Hong Kong(Project No.CUHK4180/10E)the National Basic Research Program of China(973 Program)(No.2009CB825404).
文摘One paper in a preceding issue of this journal has introduced the Bayesian Ying-Yang(BYY)harmony learning from a perspective of problem solving,parameter learning,and model selection.In a complementary role,the paper provides further insights from another perspective that a co-dimensional matrix pair(shortly co-dim matrix pair)forms a building unit and a hierarchy of such building units sets up the BYY system.The BYY harmony learning is re-examined via exploring the nature of a co-dim matrix pair,which leads to improved learning performance with refined model selection criteria and a modified mechanism that coordinates automatic model selection and sparse learning.Besides updating typical algorithms of factor analysis(FA),binary FA(BFA),binary matrix factorization(BMF),and nonnegative matrix factorization(NMF)to share such a mechanism,we are also led to(a)a new parametrization that embeds a de-noise nature to Gaussian mixture and local FA(LFA);(b)an alternative formulation of graph Laplacian based linear manifold learning;(c)a codecomposition of data and covariance for learning regularization and data integration;and(d)a co-dim matrix pair based generalization of temporal FA and state space model.Moreover,with help of a co-dim matrix pair in Hadamard product,we are led to a semi-supervised formation for regression analysis and a semi-blind learning formation for temporal FA and state space model.Furthermore,we address that these advances provide with new tools for network biology studies,including learning transcriptional regulatory,Protein-Protein Interaction network alignment,and network integration.
基金National Natural Science Foundation of China(10971121,11101243,61070230)The Research Fund for the Doctoral Program of Higher Education(20100131120017) Graduate Independent Innovation Foundation of Shandong University(yzc10040)
