共查询到20条相似文献,搜索用时 678 毫秒
1.
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. 相似文献
2.
Branko ?urgus 《Discrete Applied Mathematics》2007,155(13):1774-1792
Let S be a finite set with m elements in a real linear space and let JS be a set of m intervals in R. We introduce a convex operator co(S,JS) which generalizes the familiar concepts of the convex hull, , and the affine hull, , of S. We prove that each homothet of that is contained in can be obtained using this operator. A variety of convex subsets of with interesting combinatorial properties can also be obtained. For example, this operator can assign a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For two types of families JS we give two different upper bounds for the number of vertices of the polytopes produced as co(S,JS). Our motivation comes from a recent improvement of the well-known Gauss-Lucas theorem. It turns out that a particular convex set co(S,JS) plays a central role in this improvement. 相似文献
3.
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 . 相似文献
4.
5.
For a given structure D (digraph, multidigraph, or pseudodigraph) and an integer r large enough, a smallest inducing r-regularization of D is constructed. This regularization is an r-regular superstructure of the smallest possible order with bounded arc multiplicity, and containing D as an induced substructure. The sharp upper bound on the number, ρ, of necessary new vertices among such superstructures for n-vertex general digraphs D is determined, ρ being called the inducing regulation number of D. For being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either or (where the case is not a trivial subcase of ). 相似文献
6.
Tsz Ho Chan 《Journal of Number Theory》2008,128(5):1182-1194
We generalize Dirichlet's diophantine approximation theorem to approximating any real number α by a sum of two rational numbers with denominators 1?q1,q2?N. This turns out to be related to the congruence equation problem with 1?x,y?q1/2+?. 相似文献
7.
Richard Stong 《Discrete Mathematics》2006,306(18):2186-2204
Call a directed graph symmetric if it is obtained from an undirected graph G by replacing each edge of G by two directed edges, one in each direction. We will show that if G has a Hamilton decomposition with certain additional structure, then has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes for m?2 are decomposable into 2m+1 directed Hamilton cycles and that a product of cycles is decomposable into 2m+1 directed Hamilton cycles if ni?3 and m?2. 相似文献
8.
9.
Aneta Dudek 《Discrete Applied Mathematics》2006,154(9):1372-1379
A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is Kn-1∪K1. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph Gn of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and Pm-saturated graphs with small size. 相似文献
10.
11.
12.
Given that r and s are natural numbers and and are independent random variables where q,p∈(0,1), we prove that the likelihood ratio of the convolution Z=X+Y is decreasing, increasing, or constant when q<p, q>p or q=p, respectively. 相似文献
13.
Jonathan Lenchner 《Discrete Applied Mathematics》2011,159(7):612-620
14.
We construct n-dimensional counterparts of manifolds modeled on the space ?2 equipped by the bounded weak topology (-manifolds). For -manifolds we prove the characterization, triangulation and classification theorems. In addition, a universal map of onto Q∞ (the countable direct limit of Hilbert cubes and Z-embeddings) is constructed and characterized. 相似文献
15.
Improved bounds for acyclic chromatic index of planar graphs 总被引:1,自引:0,他引:1
16.
17.
Xiaoling Zhang 《Linear algebra and its applications》2008,428(7):1610-1619
In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K1,k and one vertex of degree n of Km,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs. 相似文献
18.
We find lower bounds on the difference between the spectral radius λ1 and the average degree of an irregular graph G of order n and size e. In particular, we show that, if n ? 4, then
19.
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, .
20.
If G is a connected graph with vertex set V, then the degree distance of G, D′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163]. 相似文献