共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
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. 相似文献
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.
7.
8.
9.
Improved bounds for acyclic chromatic index of planar graphs 总被引:1,自引:0,他引:1
10.
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 . 相似文献
11.
12.
13.
Suppose that D is an acyclic orientation of a graph G. An arc of D is dependent if its reversal creates a directed cycle. Let () denote the minimum (maximum) of the number of dependent arcs over all acyclic orientations of G. We call Gfully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying . We show that a connected graph G is fully orientable if . This generalizes the main result in Fisher et al. [D.C. Fisher, K. Fraughnaugh, L. Langley, D.B. West, The number of dependent arcs in an acyclic orientation, J. Combin. Theory Ser. B 71 (1997) 73-78]. 相似文献
14.
15.
An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3. 相似文献
16.
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. 相似文献
17.
Edith Hemaspaandra Lane A. Hemaspaandra Stanis?aw P. Radziszowski 《Discrete Applied Mathematics》2007,155(2):103-118
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:
- (1)
- , , , and .
- (2)
- For all k?2, and .
- (3)
- For all k?2, .
- (4)
- .
- (5)
- For all k?2, .
18.
Elena Liliana Popescu 《Journal of Pure and Applied Algebra》2008,212(6):1427-1431
Let be the absolute Galois group of Q and let A=C(G,C) be the Banach algebra of all continuous functions defined on G with values in C. Let be the conjugation automorphism of C and let B be the R-Banach subalgebra of A consisting of continuous functions f such that for all σ∈G. Let ‖x‖=sup{|σ(x)|:σ∈G} be the spectral norm on and let be the spectral completion of . Using a canonical isometry between and B we study the structure of the group of R-algebras automorphisms of and the structure of its subgroup of all automorphisms of which when restricted to give rise to elements of G. We introduce a topology on and prove that this last one is homeomorphic and group isomorphic to G. 相似文献
19.