共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
This note introduces the notion (d, k) Directed Moore Graphs (DMG in short), and investigates the question of their existence. A (d, k) DMG is a regular directed graph of degree d and diameter k containing the maximum number of nodes according to a certain definition. It is shown that unless d = 1 or k = 1 there are no (d, k) DMG's. 相似文献
3.
4.
This paper introduces the multimodularity concept to study structural properties for certain class of stochastic dynamic control problems through a new efficient approach. We demonstrate that this approach can substantially simplify the proofs of the main results of one recent article and provide an alternative method for two other models in the literature. 相似文献
5.
Geoffrey Exoo Joan Gimbert Nacho López José Gómez 《Discrete Applied Mathematics》2012,160(10-11):1507-1512
The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem. 相似文献
6.
R.P Anstee 《Journal of Combinatorial Theory, Series B》1981,30(1):11-20
We study graphs whose adjacency matrix S of order n satisfies the equation S + S2 = J ? K + kI, where J is a matrix of order n of all 1's, K is the direct sum on matrices of order l of all 1's, and I is the identity matrix. Moore graphs are the only solutions to the equation in the case l = 1 for which K = I. In the case k = l we can obtain Moore graphs from a solution S by a bordering process analogous to obtaining (ν, κ, λ)-designs from some group divisible designs. Other parameters are rare. We are able to find one new interesting graph with parameters k = 6, l = 4 on n = 40 vertices. We show that it has a transitive automorphism group isomorphic to C4 × S5. 相似文献
7.
Ester Giarrusso 《manuscripta mathematica》1986,54(4):381-390
We extend a method of K. Uhlenbeck for proving the partial regularity of solutions of nonlinear elliptic systems. We do not employ reverse Hölder type inequalities. 相似文献
8.
Ilse Fischer 《Journal of Combinatorial Theory, Series A》2005,111(1):37-58
We present an elementary method for proving enumeration formulas which are polynomials in certain parameters if others are fixed and factorize into distinct linear factors over Z. Roughly speaking the idea is to prove such formulas by “explaining” their zeros using an appropriate combinatorial extension of the objects under consideration to negative integer parameters. We apply this method to prove a new refinement of the Bender-Knuth (ex-)Conjecture, which easily implies the Bender-Knuth (ex-)Conjecture itself. This is probably the most elementary way to prove this result currently known. Furthermore we adapt our method to q-polynomials, which allows us to derive generating function results as well. Finally we use this method to give another proof for the enumeration of semistandard tableaux of a fixed shape which differs from our proof of the Bender-Knuth (ex-)Conjecture in that it is a multivariate application of our method. 相似文献
9.
Michael v. Rimscha 《Combinatorica》1984,4(4):339-343
We are concerned with the notion of the degree-type (D G i )i∈ω of a graphG, whereD G i is defined to be the number of vertices inG with degreei. In the first section the following results are proven:
- IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD G i andD G i+1 are both finite and different from 0, thenG is reconstructible.
- Locally finite, countably infinite graphsG, for which infinitely manyD G i are different from 0 but only finitely manyD G i are infinite, are reconstructible.
10.
《Annals of Pure and Applied Logic》2018,169(12):1369-1418
Proof-theoretic method has been successfully used almost from the inception of interpolation properties to provide efficient constructive proofs thereof. Until recently, the method was limited to sequent calculi (and their notational variants), despite the richness of generalizations of sequent structures developed in structural proof theory in the meantime. In this paper, we provide a systematic and uniform account of the recent extension of this proof-theoretic method to hypersequents, nested sequents, and labelled sequents for normal modal logic. The method is presented in terms and notation easily adaptable to other similar formalisms, and interpolant transformations are stated for typical rule types rather than for individual rules. 相似文献
11.
Guantao Chen 《Journal of Graph Theory》1990,14(4):501-508
Let G be a 2-connected graph of order n. We show that if for each pair of nonadjacent vertices x,y ∈ V(G), then G is Hamiltonian. 相似文献
12.
L. A. Shepp 《Israel Journal of Mathematics》1989,67(1):23-33
L. Dubins conjectured in 1984 that the graph on vertices {1, 2, 3, ...} where an edge is drawn between verticesi andj with probabilityp
ij=λ/max(i, j) independently for each pairi andj is a.s. connected forλ=1. S. Kalikow and B. Weiss proved that the graph is a.s. connected for anyλ>1. We prove Dubin’s conjecture and show that the graph is a.s. connected for anyλ>1/4. We give a proof based on a recent combinatorial result that forλ≦1/4 the graph is a.s. disconnected. This was already proved forλ<1/4 by Kalikow and Weiss. Thusλ=1/4 is the critical value for connectedness, which is surprising since it was believed that the critical value is atλ=1. 相似文献
13.
SeungHyun Shin 《Discrete Mathematics》2018,341(4):1125-1130
Izo() is the pseudogeometric graph for pG which satisfies the Krein equality and of which the local graph also satisfies the Krein equality. We prove that Izo() exists if and only if a spherical tight 4-design on exists. Nonexistence of infinitely many spherical tight 4-designs is well known. It gives the nonexistence of Izo() for infinitely many . Especially, Izo(4) does not exist, which was the first open case. 相似文献
14.
15.
16.
We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p1(x)/(1-x)m+1. For nonbipartite simple graphs, we get a generating function of the form p2(x)/(1-x)m+1(1+x)l. Here m is the number of vertices of the graph, p1(x) is a symmetric polynomial of degree at most m, p2(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs. 相似文献
17.
Distance-regular graphs of valency > 2, diameter m, and girth 2m with the additional property that any two points having maximal distance belong to a unique 2m circuit are investigated. It is shown that such graphs can exist only if m ≤ 3; if m = 3 only a finite number of valencies prove to be feasible. 相似文献
18.
On the total coloring of certain graphs 总被引:13,自引:0,他引:13
M. Rosenfeld 《Israel Journal of Mathematics》1971,9(3):396-402
In this paper we investigate the total chromatic number of certain graphs. In particular, we show that every cubic graph is
totally colorable in five colors. 相似文献
19.
《Discrete Mathematics》1986,58(3):275-283
It is shown that generalized Moore geometries of type GMm(s,t,c) with c = s + 1 do not exist for m = 6 and m = 7, if st > 1. 相似文献
20.
Using methods of Algebraic Graph Theory, generalized Moore geometries of type GMm(s, t, c) with c = s + 1 are investigated. It is shown that such geometries do not exist for odd values of the diameter m exceeding 7, if st>1. 相似文献