共查询到20条相似文献,搜索用时 15 毫秒
1.
Colin Cooper 《Random Structures and Algorithms》1995,6(4):439-448
A digraph D is said to be k-cyclic if every k vertices of D lie in some directed cycle of D . We show that almost every 2-regular digraph is 2-cyclic. 相似文献
2.
3.
Yahya Ould Hamidoune 《Combinatorica》1982,2(2):143-147
Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs. 相似文献
4.
A. Y. M. Chin 《Acta Mathematica Hungarica》2004,102(4):337-342
Let R be an associative ring with unit and let N(R) denote the set of nilpotent elements of R. R is said to be stronglyπ-regular if for each x∈R, there exist a positive integer n and an element y∈R such that x
n=x
n
+1
y and xy=yx. R is said to be periodic if for each x∈R there are integers m,n≥ 1 such that m≠n and x
m=x
n. Assume that the idempotents in R are central. It is shown in this paper that R is a strongly π-regular ring if and only if N(R) coincides with the Jacobson radical of R and R/N(R) is regular. Some similar conditions for periodic rings are also obtained.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
5.
6.
A note on the number of functional digraphs 总被引:1,自引:0,他引:1
Ronald C. Read 《Mathematische Annalen》1961,143(2):109-110
7.
8.
Ma?gorzata Zwonek 《Discrete Mathematics》2006,306(18):2282-2291
In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments. 相似文献
9.
10.
11.
12.
13.
The -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset of a strong digraph is a -restricted arc cut if has a strong component with order at least such that contains a connected subdigraph with order at least . The -restricted arc connectivity of a digraph is the minimum cardinality over all -restricted arc cuts of .Let be a strong digraph with order and minimum degree . In this paper, we first show that exists if and, furthermore, if , where is the minimum 3-degree of . Next, we prove that if . Finally, we give examples showing that these results are best possible in some sense. 相似文献
14.
We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex.
We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning
trees and arborescences.
We also examine the relationship between our results and certain results of Erdős and Rényi. 相似文献
15.
Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008 相似文献
16.
W. Mader 《Combinatorica》1985,5(2):161-165
It is shown that there is a digraphD of minimum outdegree 12m and
μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively. 相似文献
17.
Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c2 ≤ … ≤ cD, D > 3, as the values of its t-distance connectivities κ(2) = c2, …, κ(D) = cD. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc. 相似文献
18.
M. A. Fiol 《Journal of Graph Theory》1993,17(1):31-45
This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter lpi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l0 = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ 2 + … + ΔD (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc. 相似文献
19.
A note on connectivity of efficient solution sets 总被引:3,自引:0,他引:3
Wen Song 《Archiv der Mathematik》1995,65(6):540-545