共查询到20条相似文献,搜索用时 0 毫秒
1.
研究本原有向图的顶点指数,运用图论与数论方法,得到了n阶围长为r的本原有向图的点指数expD(k)的上界:若rn,且r为素数,D∈Dn,r={D|D为n阶本原有向图且围长为r},则expD(n,k)=rn-2r+k(1≤k≤n);若r|n,且r为素数或素数的幂,D∈Dn,r,则expD(n,1)=rn-3r+2. 相似文献
2.
John Hempel 《Inventiones Mathematicae》1982,67(1):133-142
LetMS
3,P
3 be a closed, orientable irreducible 3-manifold which admits an orientation reversing involution :MM. If dim(Fix )=0, suppose 1 (M) has a subgroup of even index. We show thatM has finite coverMMM} with 1(M<0). As an application we show that the hyperbolic dodecahedral space has a finite cover with positive 1st betti number. 相似文献
3.
4.
D.R Woodall 《Journal of Combinatorial Theory, Series B》1973,15(3):225-255
The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least disjoint edges if , at least disjoint edges if , a Hamiltonian circuit if , and a circuit of length at least if and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general. 相似文献
5.
6.
Edward F Schmeichel 《Journal of Combinatorial Theory, Series B》1981,30(2):123-129
MacLane proved that a graph is planar if and only if it has a 2-fold basis for its cycle space. We define the basis number of a graph G to be the least integer k such that G has a k-fold basis for its cycle space. We investigate the basis number of the complete graphs, complete bipartite graphs, and the n-cube. 相似文献
7.
Alfio Giarlotta 《Topology and its Applications》2005,150(1-3):157-177
For each pair of linear orderings (L,M), the representability number reprM(L) of L in M is the least ordinal α such that L can be order-embedded into the lexicographic power . The case is relevant to utility theory. The main results in this paper are as follows. (i) If κ is a regular cardinal that is not order-embeddable in M, then reprM(κ)=κ; as a consequence, for each κω1. (ii) If M is an uncountable linear ordering with the property that A×lex2 is not order-embeddable in M for each uncountable AM, then for any ordinal α; in particular, . (iii) If L is either an Aronszajn line or a Souslin line, then . 相似文献
8.
V Neumann-Lara 《Journal of Combinatorial Theory, Series B》1982,33(3):265-270
In this paper the concept of dichromatic number of a digraph which is a generalization of the chromatic number of a graph is introduced. The dichromatic number of a digraph D is defined as the minimum number of colours required to colour the vertices of D in such a way that the chromatic classes induce acyclic subdigraphs in D. Some results relating the dichromatic number of D with the existence of cycles of special lengths in D are presented. Contributions to chromatic theory are also obtained. In particular, we generalize the theorem due to P. Erdös and A. Hajnal (Acta Math. Acad. Sci. Hungar.17 (1966), 61–99) which states the existence of odd cycles of length ≥χ(G) ? 1 in any graph G. 相似文献
9.
For a connected graph G with n vertices, let {λ1,λ2,…,λr} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ1λ2…λr/n. In this paper, we study some properties and applications of the Hoffman number. 相似文献
10.
Jeffrey L. Stuart 《Czechoslovak Mathematical Journal》2009,59(3):623-636
Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families
of graphs. 相似文献
11.
Helma GladdinesMarcel van de Vel 《Topology and its Applications》2011,158(3):424-431
The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D9, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10). 相似文献
12.
V. G. Vizing 《Journal of Applied and Industrial Mathematics》2013,7(2):269-274
We introduce the notion of the semi-chromatic number of a graph with a nonempty number of edges. Then we prove that the difference between the semi-chromatic number and the half of the chromatic number is at most 1. 相似文献
13.
Other than standard election disruptions involving shenanigans, strategic voting, and so forth, it is reasonable to expect
that elections are free from difficulties. But this is far from being true; even sincere election outcomes admit all sorts
of counterintuitive conclusions. 相似文献
14.
15.
Richard G. Swan 《Mathematische Zeitschrift》1967,102(4):318-322
16.
We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc. 相似文献
17.
Futaba Okamoto Ping Zhang Varaporn Saenpholphat 《Czechoslovak Mathematical Journal》2008,58(1):271-287
For a nontrivial connected graph G of order n and a linear ordering s: v
1, v
2, …, v
n
of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t
+(G) of G is t
+(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper
traceable number of a graph. All connected graphs G for which t
+(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established.
Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand
under the grant number MRG 5080075. 相似文献
18.
Drago Bokal Gasper Fijavz Martin Juvan P. Mark Kayll Bojan Mohar 《Journal of Graph Theory》2004,46(3):227-240
We introduce the circular chromatic number χc of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χc between 1 and 2 are possible. We show that in fact, χc takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χc at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004 相似文献
19.
Semigroup Forum - For a Hausdorff topologized semilattice X its Lawson number $$\bar{\Lambda }(X)$$ is the smallest cardinal $$\kappa $$ such that for any distinct points $$x,y\in X$$ there exists... 相似文献
20.
Farhad Shahrokhi Lszl A. Szkely Ondrej Sýkora Imrich Vrt'o 《Journal of Graph Theory》1996,21(4):413-424
Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O(log2 n) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O(m2/k2) crossings on k pages. This is within a constant multiplicative factor from our general lower bound of Ω(m3/n2k2), provided that m = Ψ(n2). © 1996 John Wiley & Sons, Inc. 相似文献