共查询到20条相似文献,搜索用时 27 毫秒
1.
We count the number of complete graphs of order 4 contained in certain graphs. 相似文献
2.
Noga Alon 《Israel Journal of Mathematics》1981,38(1-2):116-130
All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forS ⊂V(H) defineN(S)={x ∈V(H):xy ∈E(H) for somey ∈S}. Define alsoδ(H)= max {|S| − |N(S)|:S ⊂V(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A.
For every graph H there are positive constants c
1, c2
such that {fx116-1}.
Theorem B.
If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H.
(It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.)
This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew
University of Jerusalem. 相似文献
3.
4.
We answer the following question: what is the minimum number of edges of a 2-connected graph with a given diameter? This problem stems from survivable telecommunication network design with grade-of-service constraints. In this paper, we prove tight bounds for 2-connected graphs and for 2-edge-connected graphs. The bound for 2-connected graphs was a conjecture of B. Bollobás (AMH 75–80) [3]. 相似文献
5.
Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T
2(n)), whereT
2(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK
r
-free graphG withn vertices. In particular, in the class of allK
r
-free graphs withn vertices the complete balanced (r – 1)-partite graphT
r–1(n) has the largest number of subgraphs isomorphic toK
t
(t < r),C
4,K
2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday 相似文献
6.
Byeong Moon Kim Byung Chul Song Woonjae Hwang 《Linear algebra and its applications》2007,420(2-3):648-662
A graph G = (V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp(G), of G. In this paper, we find the minimum number, h(n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h(n, k) edges when k is 3 or even. 相似文献
7.
For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E1 ∪ E2 ∪…? ∪ Ek, where ∣Ei∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣Ek∣ ≤ s and each Ei induces a connected subgraph of G. We prove
- (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
- (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
- (iii) If G is 3-edge connected, then there exists a 4-partition;
- (iv) If G is 4-edge connected, then there exists an s-partition for all s.
8.
Hong-Jian Lai 《Discrete Mathematics》2001,230(1-3):63-69
For an integer l0, define
to be the family of graphs such that
if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in
are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in
. Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended. 相似文献
9.
Edward A. Bender E. Rodney Canfield Brendan D. McKay 《Random Structures and Algorithms》1990,1(2):127-169
Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions wk ? 1. a(x) and φ(x) such that c(n, q) ? wk(qN)enφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (Nq) exp(–ne?2q/n). on the other hand, if k = o(n1/2), this formula simplifies to c(n, n + k) ? 1/2 wk (3/π)1/2 (e/12k)k/2nn?(3k?1)/2. 相似文献
10.
Laura A. Sanchis 《Discrete Mathematics》1995,140(1-3):149-166
A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m1 (G, D) denote the number of edges that have neither endpoint in D, and let m2 (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m1 (G, D), m2 (G, D)) can attain for connected graphs having a given domination number. 相似文献
11.
Bollobás, Erdös, Simonovits, and Szemerédi conjectured [1] that for each positive constantc there exists a constantg(c) such that ifG is any graph which cannot be made 3-chromatic by the omission ofcn 2 edges, thenG contains a 4-chromatic subgraph with at mostg(c) vertices. Here we establish the following generalization which was suggested by Erdös [2]: For each positive constantc and positive integerk there exist positive integersf k(c) andn o such that ifG is any graph with more thann o vertices having the property that the chromatic number ofG cannot be made less thank by the omission of at mostcn 2 edges, thenG contains ak-chromatic subgraph with at mostf k(c) vertices. 相似文献
12.
For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then . 相似文献
13.
F. A. Pushnyakov 《Mathematical Notes》2016,99(3-4):545-551
We obtain new estimates for the number of edges in induced subgraphs of a special distance graph. 相似文献
14.
We consider finite, undirected, and simple graphs G of order n(G) and minimum degree δ(G). The connectivity κ(G) for a connected graph G is defined as the minimum cardinality over all vertex‐cuts. If κ(G) < δ(G), then Topp and Volkmann 7 showed in 1993 for p‐partite graphs G that As a simple consequence, Topp and Volkmann obtained for p‐partite graphs G the identity κ(G) = δ(G), if In this article, we will show that these results remain true for graphs G with ω(G) ≤ p, where ω(G) denotes the clique number of G. Since each p‐partite graph G satisfies ω(G) ≤ p, this generalizes the results of Topp and Volkmann. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 7–14, 2006 相似文献
15.
Stanley Wagon 《Journal of Combinatorial Theory, Series B》1980,29(3):345-346
For each n, we obtain a (polynomial) bound on the chromatic number in terms of the maximum size of a complete subgraph, for graphs not having n · K2 as an induced subgraph. 相似文献
16.
17.
Among the graphs with a prescribed number of edges, those with maximal index are determined. The result confirms a conjecture of Brualdi and Hoffman. 相似文献
18.
Michael Krivelevich 《Combinatorica》1997,17(3):401-426
A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described. 相似文献
19.
Eyal Ackerman 《Journal of Combinatorial Theory, Series A》2007,114(3):563-571
A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones. 相似文献
20.
In this paper, we consider a class of nonlinear matrix equation of the type \(X+\sum _{i=1}^mA_i^{*}X^{-q}A_i-\sum _{j=1}^nB_{j}^{*}X^{-r}B_j=Q\), where \(0<q,\,r\le 1\) and Q is positive definite. Based on the Schauder fixed point theorem and Bhaskar–Lakshmikantham coupled fixed point theorem, we derive some sufficient conditions for the existence and uniqueness of the positive definite solution to such equations. An iterative method is provided to compute the unique positive definite solution. A perturbation estimation and the explicit expression of Rice condition number of the unique positive definite solution are also established. The theoretical results are illustrated by numerical examples. 相似文献