首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 46 毫秒
1.
Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that d-ary multi-edge trees where the out-degrees are bounded by d are in bijection with classical d-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.  相似文献   

2.
TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.  相似文献   

3.
In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space Rd by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n3). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.  相似文献   

4.
The height of a face in a 3-polytope is the maximum degree of the incident vertices of the face, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large; so we assume the absence of pyramidal faces. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, we improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20 which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. Recently, we obtained the sharp bound 10 for triangle-free 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily 3-polytopes that h ≤ 23. In this paper we improve this bound to the sharp bound 20.  相似文献   

5.
Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uvE(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that GF if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each GF, G is not Z 3-connected if and only if G is one of K 2,n?2, K 3,n?3, K 2,n?2 + , K 3,n?3 + or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].  相似文献   

6.
Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e(G) 〉 1/2(k - 1)n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 + 37/2+ 14 and every graph G on n vertices with e(G) 〉 1/2 (k- 1)n, we prove that there exists a graph G' on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.  相似文献   

7.
The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) \({\leqq}\) scp(G). Also, it is known that for every graph G on n vertices, scp(G) \({\leqq n^{2}/2}\). In this paper, among some other results, we improve this bound for scc(G). In particular, we prove that if G is a graph on n vertices with no isolated vertex and the maximum degree of the complement of G is d ? 1, for some integer d, then scc(G) \({\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}\), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem.  相似文献   

8.
A well-known result of Kupitz from 1982 asserts that the maximal number of edges in a convex geometric graph (CGG) on n vertices that does not contain \(k+1\) pairwise disjoint edges is kn (provided \(n>2k\)). For \(k=1\) and \(k=n/2-1\), the extremal examples are completely characterized. For all other values of k, the structure of the extremal examples is far from known: their total number is unknown, and only a few classes of examples were presented, that are almost symmetric, consisting roughly of the kn “longest possible” edges of CK(n), the complete CGG of order n. In order to understand further the structure of the extremal examples, we present a class of extremal examples that lie at the other end of the spectrum. Namely, we break the symmetry by requiring that, in addition, the graph admit an independent set that consists of q consecutive vertices on the boundary of the convex hull. We show that such graphs exist as long as \(q \le n-2k\) and that this value of q is optimal. We generalize our discussion to the following question: what is the maximal possible number f(nkq) of edges in a CGG on n vertices that does not contain \(k+1\) pairwise disjoint edges, and, in addition, admits an independent set that consists of q consecutive vertices on the boundary of the convex hull? We provide a complete answer to this question, determining f(nkq) for all relevant values of nk and q.  相似文献   

9.
We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with pR2 and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {xR2: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.  相似文献   

10.
The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log? n?logf max) times the sum of the skeleton lengths of the individual polytopes.  相似文献   

11.
We prove that among all flag 3-manifolds on n vertices, the join of two circles with ?n/2? and ?n/2? vertices respectively is the unique maximizer of the face numbers. This solves the first case of a conjecture due to Lutz and Nevo. Further, we establish a sharp upper bound on the number of edges of flag 5-manifolds and characterize the cases of equality. We also show that the inequality part of the flag upper bound conjecture continues to hold for all flag 3-dimensional Eulerian complexes and find all maximizers of the face numbers in this class.  相似文献   

12.
A k-coloring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5-coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2-coloring in which each color class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic t-improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.  相似文献   

13.
Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.  相似文献   

14.
Each Platonic polyhedron P can be folded using a continuous folding process into a face of P so that the resulting shape is flat and multilayered, while two of the faces are rigid during the motion. In previous works, explicit formulas of continuous functions for such motions were given and the same result as above was shown to hold for any tetrahedron. In this paper, we show that a truncated regular tetrahedron can be folded continuously via explicit continuous folding mappings into a flat (folded) state, such that two of the hexagonal faces are rigid. Furthermore, given any general tetrahedron P and any truncated tetrahedron Q of P, we show that if Q contains the largest inscribed sphere of P and satisfies some condition, then Q can be folded continuously into a flat folded state such that two of the hexagonal faces of Q are rigid during the motion.  相似文献   

15.
For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs.  相似文献   

16.
For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V 1?V 2 such that G has at most s edges with both incident vertices in V i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.  相似文献   

17.
We show that for every ? > 0 there exist δ > 0 and n0 ∈ ? such that every 3-uniform hypergraph on nn0 vertices with the property that every k-vertex subset, where kδn, induces at least \(\left( {\frac{1}{2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)\) edges, contains K4? as a subgraph, where K4? is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erd?s and Sós. The constant 1/4 is the best possible.  相似文献   

18.
We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.  相似文献   

19.
Let CC d,k be the largest possible number of vertices in a cyclic Cayley graph of degree d and diameter k, and let AC d,k be the largest order in an Abelian Cayley graph for given d and k. We show that \({CC_{d,2} \geq \frac{13}{36} (d + 2)(d -4)}\) for any d= 6p?2 where p is a prime such that \({p \neq 13}\) , \({p \not\equiv 1}\) (mod 13), and \({AC_{d,3} \geq \frac{9}{128} (d + 3)^2(d - 5)}\) for d = 8q?3 where q is a prime power.  相似文献   

20.
The vertices of the commuting graph of a semigroup S are the noncentral elements of this semigroup, and its edges join all pairs of elements g, h that satisfy the relation gh = hg. The paper presents a proof of the fact that the diameter of the commuting graph of the semigroup of real matrices of order n ≥ 3 is equal to 4. A survey of results in that subject matter is presented, and several open problems are formulated.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号