共查询到20条相似文献,搜索用时 31 毫秒
1.
设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$. 相似文献
2.
We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001 相似文献
3.
4.
给定一个赋权图$G=(V,E;w,c)$以及图$G$的一个支撑子图$G_{1}=(V,E_{1})$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w:E\rightarrow\mathbb{R}^{+}$,费用函数$c:E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c(E_{2})$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c(E_{2})$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。 相似文献
5.
给定一个赋权图$G=(V,E;w,c)$以及图$G$的一个支撑子图$G_{1}=(V,E_{1})$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w:E\rightarrow\mathbb{R}^{+}$,费用函数$c:E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c(E_{2})$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c(E_{2})$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。 相似文献
6.
Heinke Conrads 《manuscripta mathematica》2002,107(2):215-227
We derive a classification algorithm for reflexive simplices in arbitrary fixed dimension. It is based on the assignment
of a weight Q ? ℕ
n+1
to an integral n-simplex, the construction, up to an isomorphism, of all simplices with given weight Q, and the characterization in terms of the weight as to when a simplex with reduced weight is reflexive. This also yields
a convex-geometric reproof of the characterization in terms of weights for weighted projective spaces to have at most Gorenstein
singularities.
Received: 30 March 1999 / Revised version: 18 October 2001 相似文献
7.
William McCuaig 《Journal of Graph Theory》2001,38(3):124-169
A brace is a connected bipartite graph with a perfect matching and at least six vertices such that for every pair of nonadjacent edges, there is a perfect matching containing the edges. We give a method for generating all braces. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 124–169, 2001 相似文献
8.
We investigate a system of delayed lattice differential system which is a model of pioneer-climax species distributed on one dimensional discrete space. We show that there exists a constant $c^*>0$, such that the model has traveling wave solutions connecting a boundary equilibrium to a co-existence equilibrium for $c\geq c^*$. We also argue that $c^*$ is the minimal wave speed and the delay is harmless. The Schauder's fixed point theorem combining with upper-lower solution technique is used for showing the existence of wave solution. 相似文献
9.
In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers
to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge
bounds equal one, stable multi-sets are equivalent to stable sets.
For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient
conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the
stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable
multi-sets and conditions for them to be facet defining are determined.
The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets
emerge as an important substructure in the design of optical networks.
Received: February 14, 2001/Revised version: September 7, 2001 相似文献
10.
Zhangmin HUANG 《数学年刊B辑(英文版)》2020,41(2):163-176
Let π : M~n→P~n be an n-dimensional small cover over P~n and λ : F(P~n)→Z_2~n be its characteristic function. The author uses the symbol c(λ) to denote the cardinal number of the image Im(λ). If c(λ) = n + 1 or n + 2, then a necessary and sufficient condition on the existence of spin structure on Mnis given. As a byproduct, under some special conditions, the author uses the second Stiefel-Whitney class to detect when P~n is n-colorable or(n + 1)-colorable. 相似文献
11.
12.
Chuang-yin Dang 《计算数学(英文版)》2006,24(6):711-718
A mapping f:Z~n→R~n is said to possess the direction preserving property if fi(x)>0implies fi(y)≥0 for any integer points x and y with ‖x-y‖∞≤1.In this paper,a simplicial algorithm is developed for computing an integer zero point of a mappingwith the direction preserving property.We assume that there is an integer point x~0 withc≤x~0≤d satisfying that max_(1≤i≤n)(x_i-x_i~0)fi(x)>0 for any integer point x withf(x)≠0 on the boundary of H={x∈R~n|c-e≤x≤d e},where c and d are twofinite integer points with c≤d and e=(1,1,…1)~∈R~n.This assumption is impliedby one of two conditions for the existence of an integer zero point of a mapping with thepreserving property in van der Laan et al.(2004).Under this assumption, starting at x~0,the algorithm follows a finite simplicial path and terminates at an integer zero point ofthe mapping.This result has applications in general economic equilibrium models withindivisible commodities. 相似文献
13.
14.
In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number. 相似文献
15.
We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999 相似文献
16.
$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界. 相似文献
17.
符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$. 相似文献
18.
19.
Piotr Gwiazda 《Mathematical Methods in the Applied Sciences》2001,24(3):159-178
This paper proves global in time existence of large solutions for a problem in non‐linear inelasticity with viscosity given by the term $cL\partial_tu$\nopagenumbers\end . In addition we study singular limits $c\mapsto0$\nopagenumbers\end . The proofs are based on energy methods. Copyright © 2001 John Wiley & Sons, Ltd. 相似文献
20.
Daniel P. Sanders 《Journal of Graph Theory》1996,21(3):317-322
This paper presents an inequality satisfied by planar graphs of minimum degree five. For the purposes of this paper, an edge of a graph is light if the weight of the edge, or the sum of the degrees of the vertices incident with it, is at most eleven. The inequality presented shows that planar graphs of minimum degree five have a large number of light edges. This inequality improves upon a recent inequality of Borodin and Sanders, which showed that 7/15 times the number of edges of weight 10 plus 1/5 times the number of edges of weight 11 is at least 12. These constants 7/15 and 1/5 were shown to be best possible. The inequality in this paper shows that, for this type of graph, the presence of vertices of degree at least eight increases the number of light edges. A graph is presented which shows that the coefficient obtained for the number of degree eight vertices is best possible. © 1996 John Wiley & Sons, Inc. 相似文献