检索结果-南通市图书馆

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH maximum degree

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Acta Mathematica Scientia 2006年第3期26卷 477-482页

作者：张忠辅王维凡李敬文姚兵卜月华 College of Mathematics and Information Science Northwest Normal University Lanzhou 730070China Institute of Applied MathematicsLanzhou Jiaotong UniversityLanzhou 730070China Department of Mathematics ZheJiang Normal University Jinhua 321004China School of Information and Electrical Engineering Lanzhou Jiaotong University Lanzhou 730070China College of Mathematics and Information Science Northwest Normal University Lanzhou 730070China

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... 详细信息

关键词： Plane graph edge-face chromatic number edge chromatic number maximum degree

The maximum and Minimum degree of the Random r-uniform r-partite Hypergraphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2016年第4期32卷 867-874页

作者： Ai-lian CHEN Hao LI Fu-ji ZHANG College of Mathematics and Computer Science Fuzhou University Fuzhou 350108 China Laboratoire de Recherche en Informatique UMR 8623 C. N. R. S. -Universite de Paris-sud 91405-Orsay cedex France School of Mathematical Sciences Xiamen University Xiamen 361005 China

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.

关键词： maximum degree minimum degree degree distribution random uniform hypergraphs

AN INEQUALITY RELATING THE ORDER, maximum degree, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 1992年第2期8卷 144-152页

作者：徐俊明 University of Science and Technology of China Hefei 230026 Chinae prove that if there is a strongly connected digraph of order n maximum degree ddiameter 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.

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.

关键词： DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH maximum degree AN INEQUALITY RELATING THE ORDER

Injective △+2 Coloring of Planar Graph Without Short Cycles

在线全文

学校读者我要写书评

暂无评论

应用数学学报:英文版 2023年第4期39卷 1009-1031页

作者： Ying CHEN Lan TAO Li ZHANG School of Mathematical Sciences Tongji UniversityShanghai 200092China

A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.

关键词： injective coloring planar graph maximum degree cycle

List 2-distance Coloring of Planar Graphs with Girth Five

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 2022年第3期38卷 540-548页

作者： Yin-dong JIN Lian-ying MIAO School of Mathematics China University of Mining and TechnologyXuzhou 221116China

A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors.A list assignment of a graph G is a mapping L which assigns to each vertex v a set L(v)of positive integers.The list 2-distance chromatic number of G denoted byχ_(2)^(l)(G)is the least integer k for which G is list 2-distance k-colorable.In this paper,we prove that every planar graph with g(G)≥5 and△(G)≥40 is list 2-distance(△(G)+4)-colorable.

关键词： 2-distance coloring list 2-distance coloring girth maximum degree

Strict Neighbor-Distinguishing Total Index of Graphs

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2022年第4期38卷 770-776页

作者： Jing GU Wei Fan WANG Yi Qiao WANG Department of Mathematics Zhejiang Normal UniversityJinhua 321004P.R.China School of Management Beijing University of Chinese MedicineBeijing 100029P.R.China

A total-coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v,the set of colors used on u and its incident edges and the set of colors used on v and its incident edges are not included with each other.The strict neighbor-distinguishing total indexχ"_(snd)(G)of G is the minimum number of colors in a strict neighbor-distinguishing total-coloring of G.In this paper,we prove that every simple graph G withΔ(G)≥3 satisfiesχ"_(snd)(G)≤2Δ(G).

关键词： Strict neighbor-distinguishing total-coloring Strict neighbor-distinguishing total index maximum degree

Acyclic Choosability of Graphs with Bounded degree

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2022年第3期38卷 560-570页

作者： Juan WANG Lian Ying MIAO Jin Bo LI Yun Long LIU School of Management Qufu Normal UniversityRizhao276826P.R.China School of Mathematics China University of Mining and TechnologyXuzhou221116P.R.China College of Engineering Qufu Normal UniversityRizhao276826P.R.China

An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = {L(v)| v∈V(G)}, if there exists an acyclic colouringρ such that ρ(v)∈L(v) for each v∈V(G), then ρ is called an acyclic L-list colouring of G. If there exists an acyclic L-list colouring of G for any L with |L(v)|≥k for each v∈V(G), then G is called acyclically k-choosable. In this paper, we prove that every graph with maximum degree Δ≤7 is acyclically 13-choosable. This upper bound is first proposed. We also make a more compact proof of the result that every graph with maximum degree Δ≤3(resp., Δ≤4) is acyclically 4-choosable(resp., 5-choosable).

关键词： Acyclic choosability list colouring acyclic colouring maximum degree

THE maximum AND MINIMUM degreeS OF RANDOM BIPARTITE MULTIGRAPHS

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Scientia 2011年第3期31卷 1155-1166页

作者：陈爱莲张福基李皓 College of Mathematics and Computer Science Fuzhou University School of Mathematical Sciences Xiamen University Laboratoire de Recherche en Informatique UMR 8623 C. N. R. S.-Université de Paris-sud

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？

关键词： maximum degree minimum degree degree distribution random bipartite multigraphs

On a Classical Theorem on the Diameter and Minimum degree of a Graph

在线全文

学校读者我要写书评

暂无评论

Acta Mathematica Sinica,English Series 2017年第11期33卷 1477-1503页

作者： Veronica HERNANDEZ Domingo PESTANA Jose M. RODRIGUEZ Universidad CarlosⅢde Madrid Avenida de la Universidad3028911 LeganesSpain

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erdos, Pach, Pollack and Tuza. We use these bounds in order to study hyperbolic graphs （in the Gromov sense）. To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H（n, δ0） be the set of graphs G with n vertices and minimum degree 50, and J（n, Δ） be the set of graphs G with n vertices and maximum degree A. We study the four following extremal problems on graphs： a（n,δ0） = min{δ（G）｜ G ∈H（n, δ0）}, b（n, δ0） =- max{δ（G）｜ e ∈H（n, δ0）}, α（n, Δ） = min{δ（G） [ G ∈ J（n, Δ）} and β（n,Δ） = max{δ（G） ] G∈Π（n,Δ）}. In particular, we obtain bounds for b（n, δ0） and we compute the precise value of a（n, δ0）, α（n, Δ） and w（n, Δ） for all values of n, r0 and A, respectively.

关键词： Extremal problems on graphs diameter minimum degree maximum degree Gromov hyperbolicity hyperbolicity constant finite graphs