共查询到20条相似文献,搜索用时 0 毫秒
1.
This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number p/q + 1, where p and q are two relatively prime numbers must have cycle rank at least p + q ? 1. A special case of this result yields that the real flow number of a 2‐connected cubic graph with chromatic index 4 and order at most 8k + 4 is bounded from below by 4 + 1/k. Using this bound we prove that the real flow number of the Isaacs snark I2k + 1 equals 4 + 1/k, completing the upper bound due to Steffen [Steffen, J Graph Theory 36 (2001), 24–34]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 11–16, 2008 相似文献
2.
3.
Bill Jackson 《Journal of Graph Theory》1991,15(4):443-451
Let G be a graph on n vertices and N2(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3-connected and N2(G) ? ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N2(G) ? ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs. 相似文献
4.
Thomas Niessen 《Journal of Graph Theory》1995,19(1):45-64
We examine bounds on the size of the neighborhood union for two (independent) vertices of a graph that imply the existence of regular factors. © 1995 John Wiley & Sons, Inc. 相似文献
5.
Neighborhood unions and cyclability of graphs 总被引:1,自引:0,他引:1
A graph G is said to be cyclable if for each orientation
of G, there exists a set S of vertices such that reversing all the arcs of
with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x1, x2 and x3, |N(x1)N(x2)|+|N(x2)N(x3)|+|N(x3)N(x1)|2n+1, then G is cyclable. 相似文献
6.
7.
We generalize a known sufficient condition for the traceability of a graph to a condition for the existence of a spanning tree with a bounded number of leaves. Both of the conditions involve neighborhood unions. Further, we present two results on spanning spiders (trees with a single branching vertex). We pose a number of open questions concerning extremal spanning trees. 相似文献
8.
M. Yu. Khachai E. D. Neznakhina 《Proceedings of the Steklov Institute of Mathematics》2015,289(1):111-125
We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly NP-hard in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora’s approach is built. 相似文献
9.
The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph 总被引:1,自引:0,他引:1
Ying-Ying Tan 《Linear algebra and its applications》2010,433(4):790-2155
In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph. 相似文献
10.
11.
12.
J.M. Alonso-Meijide M. lvarez-Mozos M.G. Fiestras-Janeiro 《Mathematical Social Sciences》2009,58(2):202-213
Two new values for transferable utility games with graph restricted communication and a priori unions are introduced and characterized. Moreover, a comparison between these and the Owen graph value is provided. These values are used to analyze the distribution of power in the Basque Parliament emerging from elections in April 2005. 相似文献
13.
14.
V.G. Vizing has shown that the edge-chromatic number of any graph with maximum vertex-degree ρ is equal to either ρ or ρ + 1. In this paper, we describe various ways of constructing graphs whose edge-chromatic number is ρ + 1 and formulate a conjecture about such graphs. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
20.
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). 相似文献