The pseudograph -threshold number

详细信息    查看全文

• 作者：Anthony J.W. Hilton^a ; ^b ; ^{a.j.w.hilton@reading.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Anitha Rajkumar^b ; ^{a.rajkumar@qmul.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph theory ; Factorization ; Edge colourings ; Threshold number ; Bipartite graph ; Pseudograph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 August 2016
• 年：2016
• 卷：209
• 期：Complete
• 页码：153-163
• 全文大小：397 K

文摘

For d≥1,s≥0$d\ge 1,s\ge 0$, a (d,d+s)$(d,d+s)$-graph   is a graph whose degrees all lie in the interval {d,d+1,…,d+s}$\{d,d+1,\dots ,d+s\}$. For r≥1,a≥0$r\ge 1,a\ge 0$, an (r,r+a)$(r,r+a)$-factor   of a graph G$G$ is a spanning (r,r+a)$(r,r+a)$-subgraph of G$G$. An (r,r+a)$(r,r+a)$-factorization   of a graph G$G$ is a decomposition of G$G$ into edge-disjoint (r,r+a)$(r,r+a)$-factors. A pseudograph is a graph which may have multiple edges and may have multiple loops. A loop counts two towards the degree of the vertex it is on. A multigraph here has no loops.

For t≥1$t\ge 1$, let π(r,s,a,t)$\pi (r,s,a,t)$ be the least integer such that, if d≥π(r,s,a,t)$d\ge \pi (r,s,a,t)$ then every (d,d+s)$(d,d+s)$-pseudograph G$G$ has an (r,r+a)$(r,r+a)$-factorization into x$x$(r,r+a)$(r,r+a)$-factors for at least t$t$ different values of x$x$. We call π(r,s,a,t)$\pi (r,s,a,t)$ the pseudograph  (r,s,a,t)$(r,s,a,t)$-threshold number  . Let μ(r,s,a,t)$\mu (r,s,a,t)$ be the analogous integer for multigraphs. We call μ(r,s,a,t)$\mu (r,s,a,t)$ the multigraph  (r,s,a,t)$(r,s,a,t)$-threshold number. A simple graph   has at most one edge between any two vertices and has no loops. We let σ(r,s,a,t)$\sigma (r,s,a,t)$ be the analogous integer for simple graphs. We call σ(r,s,a,t)$\sigma (r,s,a,t)$ the simple graph  (r,s,a,t)$(r,s,a,t)$-threshold number.

In this paper we give the precise value of the pseudograph π(r,s,a,t)$\pi (r,s,a,t)$-threshold number for each value of r,s,a$r,s,a$ and t$t$. We also use this to give good bounds for the analogous simple graph and multigraph threshold numbers σ(r,s,a,t)$\sigma (r,s,a,t)$ and μ(r,s,a,t)$\mu (r,s,a,t)$.