Article Outline
- 1. Introduction
- 2. Optimal sets for (≤k)-edge vectors
- 3. A lower bound for (≤k)-facets in
- 4. Conclusions and open problems
- Acknowledgements
- References
![]() |
|||||||
|
|||||||
共查询到20条相似文献,搜索用时 15 毫秒
1.
Felix Lazebnik 《Journal of Graph Theory》1989,13(2):203-214
Let F denote the family of simple undirected graphs on v vertices having e edges ((v, e)-graphs) and P(λ, G) be the chromatic polynomial of a graph G. For the given integers v, e, Δ, let f(v, e, Δ) denote the greatest number of proper colorings in Δ or less colors that a (v, e)-graph G can have, i.e., f(v, e, Δ) = max{P(Δ, G): G ∈ F}. In this paper we determine f(v, e, 2) and describe all graphs G for which P(2, G) = f(v, e, 2). For f(v, e, 3), a lower bound and an upper bound are found. 相似文献
2.
Owen D. Byer 《Journal of Graph Theory》1998,28(3):115-128
Let f(v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f(v, e, λ). In particular, a new notion of pseudo-proper colorings of a graph is given, which allows us to significantly improve the upper bounds for f(v, e, 3) given by Lazebnik and Liu in the case where e > v2/4. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 115–128, 1998 相似文献
3.
Ladislav Stacho 《Journal of Graph Theory》2001,36(2):117-120
We show that for any graph G, the chromatic number χ(G) ≤ Δ2(G) + 1, where Δ2(G) is the largest degree that a vertex ν can have subject to the condition that ν is adjacent to a vertex whose degree is at least as big as its own. Moreover, we show that the upper bound is best possible in the the following sense: If Δ2(G) ≥ 3, then to determine whether χ(G) ≤ Δ2(G) is an NP‐complete problem. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 117–120, 2001 相似文献
4.
Andrey B. Kupavskii Andrei M. Raigorodskii Maria V. Titova 《Discrete Mathematics》2013,313(22):2566-2574
In this paper we study the distance Ramsey number . The distance Ramsey number is the minimum number such that for any graph on vertices, either contains an induced -vertex subgraph isomorphic to a distance graph in or contains an induced -vertex subgraph isomorphic to the distance graph in . We obtain the upper and lower bounds on , which are similar to the bounds for the classical Ramsey number . 相似文献
5.
Richard C. Brewster Christina M. Mynhardt Laura E. Teshima 《Central European Journal of Mathematics》2013,11(7):1334-1343
A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ v∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λb(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λb. 相似文献
6.
7.
Manouchehr Zaker 《Journal of Graph Theory》2008,58(2):110-122
In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11 . Next, we obtain an upper bound of the order of magnitude for the coloring number of a graph with small K2,t (as subgraph), where n is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:110–122, 2008 相似文献
8.
We generalize the result of Davenport on the sum of absolute values of discriminants of integer polynomials of degree three. For the first time, we find the exact upper bound for the number of polynomials with given discriminant in the class of cubic polynomials of bounded height for the whole interval of values of discriminants. 相似文献
9.
Plamen Stefanov 《Journal of Functional Analysis》2006,231(1):111-142
We study the scattering poles of a compactly supported “black box” perturbations of the Laplacian in Rn, n odd. We prove a sharp upper bound of the counting function N(r) modulo o(rn) in terms of the counting function of the reference operator in the smallest ball around the black box. In the most interesting cases, we prove a bound of the type N(r)?Anrn+o(rn) with an explicit An. We prove that this bound is sharp in a few special spherically symmetric cases where the bound turns into an asymptotic formula. 相似文献
10.
Carl Johan Casselgren Hrant H. Khachatrian Petros A. Petrosyan 《Discrete Mathematics》2018,341(3):627-637
An interval-coloring of a multigraph is a proper edge coloring with colors such that the colors of the edges incident with every vertex of are colored by consecutive colors. A cyclic interval-coloring of a multigraph is a proper edge coloring with colors such that the colors of the edges incident with every vertex of are colored by consecutive colors, under the condition that color is considered as consecutive to color . Denote by () and () the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph , respectively. We present some new sharp bounds on and for multigraphs satisfying various conditions. In particular, we show that if is a -connected multigraph with an interval coloring, then . We also give several results towards the general conjecture that for any triangle-free graph with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most . 相似文献
12.
《Insurance: Mathematics and Economics》1987,6(4):289-293
An analytical expression for an upper bound of the stop-loss premium for the individual model is given. 相似文献
13.
Lutz Volkmann 《Aequationes Mathematicae》2013,86(3):279-287
Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f 1,f 2, . . . ,f d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs. 相似文献
14.
Oswin Aichholzer Jesús García David Orden Pedro Ramos 《European Journal of Combinatorics》2009,30(7):1568
In this paper we present two different results dealing with the number of (≤k)-facets of a set of points:
Article Outline
1. IntroductionIn this paper we deal with the problem of giving lower bounds to the number of (≤k)-facets of a set of points S. An oriented simplex with vertices at points of S is said to be a k-facet of S if it has exactly k points in the positive side of its affine hull. Similarly, the simplex is said to be an (≤k)-facet if it has at most k points in the positive side of its affine hull. If , a k-facet of S is usually named a k-edge.The number of k-facets of S is denoted by ek(S), and is the number of (≤k)-facets (the set S will be omitted when it is clear from the context). Giving bounds on these quantities, and on the number of the companion concept of k-sets, is one of the central problems in Discrete and Computational Geometry, and has a long history that we will not try to summarize here. Chapter 8.3 in [4] is a complete and up to date survey of results and open problems in the area.Regarding lower bounds for Ek(S), which is the main topic of this paper, the problem was first studied by Edelsbrunner et al. [6] due to its connections with the complexity of higher order Voronoi diagrams. In that paper it was stated that, in ,2. Optimal sets for (≤k)-edge vectorsGiven , let us denote by the set of all (≤k)-edges of S; hence Ek(S) is the cardinality of . Throughout this section we consider . Recall that for a fixed such k, Ek(S) is optimal if . Recall also that, by definition, a j-edge has exactly j points of S in the positive side of its affine hull, which in this case is the open half-plane to the right of its supporting line.We start by giving a new, simple, and self-contained proof of the bound in Eq. (1), using a new technique which will be useful in the rest of the section. Although in this section they will be used in , the following notions are presented in for the sake of generality and in view of Section 3.Definition 1 [7] Let S be a set of n points and a family of sets in . A subset NS is called an -net of S (with respect to ) if for every such that |H∩S|>n we have that H∩N≠.Definition 2 A simplicial -net of is a set of d+1 vertices of the convex hull of S that are an -net of S with respect to closed half-spaces. A simplicial -net will be called a simplicial half-net.Lemma 3 Every set of n points has a simplicial half-net.Proof Let T be a triangle spanned by three vertices of the convex hull of S. An edge e of T is called good if the closed half-plane of its supporting line which contains the third vertex of T contains at least points from S. T is called good if it consists of three good edges. Clearly, the vertices of a good triangle T are a simplicial half-net of S; the vertices of T being of the convex hull implies that the intersection of S with a half-plane not containing any vertex of T lies in the complement of some of the three half-planes defined by the good edges.Let T be an arbitrary triangle spanned by vertices of the convex hull of S and assume that T is not good. Then observe that only one edge e of T is not good and let v be the vertex of T not incident to e. Choose a point v′ of the convex hull of S opposite to v with respect to e. Then e and v′ induce a triangle T′ in which e is a good edge. If T′ is a good triangle we are done. Otherwise we iterate this process. As the cardinalities of the subsets of vertices of S considered are strictly decreasing (the subsets being restricted by the half-plane induced by e), the process terminates with a good triangle. □Theorem 4 For every set S of n points and we have .Proof The proof goes by induction on n. From Lemma 3, we can guarantee the existence of T={a,b,c}S, an -net made up with vertices of the convex hull.Let S′=ST and consider an edge . We observe that T cannot be to the right of e: there are at least points on the closed half-plane to the left of e and that would contradict the definition of -net. Therefore, .If we denote by the set of (≤k)-edges of S incident to points in T, we have that
15.
16.
17.
18.
Let G be an (mg, mf)-graph, where g and f are integer-valued functions defined on V(G) and such that 0≤g(x)≤f(x) for each x ∈ V(G). It is proved that(1) If Z ≠ , both g and f may be not even, G has a (g, f)-factorization, where Z = {x ∈ V(G): mf(x)-dG(x)≤t(x) or dG(x)-mg(x)≤ t(x), t(x)= f(x)-g(x)>0}.(2) Let G be an m-regular graph with 2n vertices, m≥n. If (P1, P2,..., Pr) is a partition of m, P1 ≡ m (mod 2), Pi ≡ 0 (mod 2), i = 2,..., r, then the edge set E(G) of G can be parted into r parts E1 , E2,...,Er of E(G) such that G[Ei] is a Pi-factor of G. 相似文献
19.
Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs. 相似文献
20.
Suppose G is a graph and λ1,λ2,…,λn are the eigenvalues of G. The Estrada index EE(G) of G is defined as the sum of eλi, 1≤i≤n. In this paper some new upper bounds for the Estrada index of bipartite graphs are presented. We apply our result on a (4,6)-fullerene to improve our bound given in an earlier paper. 相似文献
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |