共查询到20条相似文献,搜索用时 15 毫秒
1.
Improved bounds for acyclic chromatic index of planar graphs 总被引:1,自引:0,他引:1
2.
3.
4.
Two classes of edge domination in graphs 总被引:2,自引:0,他引:2
Baogen Xu 《Discrete Applied Mathematics》2006,154(10):1541-1546
Let (, resp.) be the number of (local) signed edge domination of a graph G [B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189]. In this paper, we prove mainly that and hold for any graph G of order n(n?4), and pose several open problems and conjectures. 相似文献
5.
6.
A discrete function f defined on Zn is said to be logconcave if for , , . A more restrictive notion is strong unimodality. Following Barndorff-Nielsen [O. Barndorff-Nielsen, Unimodality and exponential families, Commun. Statist. 1 (1973) 189-216] a discrete function is called strongly unimodal if there exists a convex function such that if . In this paper sufficient conditions that ensure the strong unimodality of a multivariate discrete distribution, are given. Examples of strongly unimodal multivariate discrete distributions are presented. 相似文献
7.
Angelika Hellwig 《Discrete Applied Mathematics》2008,156(17):3325-3328
Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let be the complement of G.In this article we prove that either λ(G)=δ(G) or . In addition, we present the Nordhaus-Gaddum type result . A family of examples will show that this inequality is best possible. 相似文献
8.
9.
Adrian Kosowski 《Discrete Applied Mathematics》2009,157(2):321-329
Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph G: its edge forwarding index π(G), arc forwarding index , undirected optical index , and directed optical index .In the paper we address two long-standing open problems: whether the equality holds for all graphs, and whether indices π(G) and are hard to compute. For the first problem, we give an example of a family of planar graphs {Gk} such that . For the second problem, we show that determining either π(G) or is NP-hard. 相似文献
10.
11.
Jin-Hui Fang 《Discrete Applied Mathematics》2008,156(15):2950-2958
It is conjectured by Erd?s, Graham and Spencer that if 1≤a1≤a2≤?≤as are integers with , then this sum can be decomposed into n parts so that all partial sums are ≤1. This is not true for as shown by a1=?=an−2=1, . In 1997 Sandor proved that Erd?s-Graham-Spencer conjecture is true for . Recently, Chen proved that the conjecture is true for . In this paper, we prove that Erd?s-Graham-Spencer conjecture is true for . 相似文献
12.
13.
14.
Bc(G) denotes the cyclic bandwidth of graph G. In this paper, we obtain the maximum cyclic bandwidth of graphs of order p with adding an edge as follows:
15.
16.
17.
Gintaras Palubeckis 《Discrete Applied Mathematics》2010,158(18):2075-2080
For a graph G and its complement , we define the graph coloring polytope P(G) to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G. We show that for an antiweb in G the corresponding inequality is facet-inducing for P(G) if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities. 相似文献
18.
19.
20.
Janez Mr?un 《Journal of Pure and Applied Algebra》2007,210(1):267-282
For any étale Lie groupoid G over a smooth manifold M, the groupoid convolution algebra of smooth functions with compact support on G has a natural coalgebra structure over the commutative algebra which makes it into a Hopf algebroid. Conversely, for any Hopf algebroid A over we construct the associated spectral étale Lie groupoid over M such that is naturally isomorphic to G. Both these constructions are functorial, and is fully faithful left adjoint to . We give explicit conditions under which a Hopf algebroid is isomorphic to the Hopf algebroid of an étale Lie groupoid G. 相似文献