共查询到20条相似文献,搜索用时 0 毫秒
1.
Stephen B Maurer 《Journal of Combinatorial Theory, Series B》1973,15(2):121-145
Several graph-theoretic notions applied to matroid basis graphs in the preceding paper are now tied more specifically to aspects of matroids themselves. Factorizations of basis graphs and disconnections of neighborhood subgraphs are related to matroid separations. Matroids are characterized whose basis graphs have only one or two of the three types of common neighbor subgraphs. The notion of leveling is generalized and related to matroid sums, minors, and duals. Also, the problem of characterizing regular and graphic matroids through their basis graphs is discussed. Throughout, many results are obtained quite easily with the aid of certain pseudo-combivalence systems of 0–1 matrices. 相似文献
2.
Noboru Ito 《Graphs and Combinatorics》1985,1(1):57-64
In order to provide an algebraic graph theoretic background for Hadamard matrices and designs Hadamard graphs are introduced
and their spectra are determined. 相似文献
3.
4.
This paper is the first article in a series devoted to the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this ‘precoloring’ be extended to a proper coloring of G with at most k colors (for some given k)? This question was motivated by practical problems in scheduling and VLSI theory. Here we investigate its complexity status for interval graphs and for graphs with a bounded treewidth. 相似文献
5.
Stephen B. Maurer 《Discrete Mathematics》1975,11(2):147-159
An interval in a graph is a subgraph induced by all the vertices on shortest paths between two given vertices. Intervals in matroid basis graphs satisfy many nice properties. Key results are: (1) any two vertices of a basis graph are together in some longest interval; (2) every basis graph with the minimum number of vertices for its diameter is an interval, indeed a hypercube. (1) turns out to be a simple case of a theorem in Edmonds' theory of matroid partition. 相似文献
6.
7.
8.
9.
10.
11.
12.
Eugene L. Lawler 《Mathematical Programming》1975,9(1):31-56
LetM
1 = (E, 91),M
2 = (E, 92) be two matroids over the same set of elementsE, and with families of independent sets 91, 92. A setI 91 92 is said to be anintersection of the matroidsM
1,M
2. An important problem of combinatorial optimization is that of finding an optimal intersection ofM
1,M
2. In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements. The other two algorithms compute intersections which are of maximum total weight, for a given weighting of the elements inE. One of these algorithms is primal-dual, being based on duality considerations of linear programming, and the other is primal. All three algorithms are based on the computation of an augmenting sequence of elements, a generalization of the notion of an augmenting path from network flow theory and matching theory. The running time of each algorithm is polynomial inm, the number of elements inE, and in the running times of subroutines for independence testing inM
1,M
2. The algorithms provide constructive proofs of various important theorems of matroid theory, such as the Matroid Intersection Duality Theorem and Edmonds' Matroid Polyhedral Intersection Theorem.Research sponsored by the Air Force Office of Scientific Research Grant 71-2076. 相似文献
13.
András Telcs 《Probability Theory and Related Fields》1990,85(4):489-497
Summary In this paper we consider the nearest neighbour Random Walk on infinite graphs. We discuss the connection between the two smallest eigenvalues of the Laplacian of the graph and the diffusion speed of the RW. 相似文献
14.
Marc Chastand 《Discrete Mathematics》2006,306(13):1272-1284
We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K1, the path K1,2 and the 4-cycle K2,2, and the two-connected K4- and K1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class. 相似文献
15.
16.
LinYixun 《高校应用数学学报(英文版)》2000,15(2):184-192
Abstract. The basis graph G for a linear programming consists of all bases under pivot transfor-mations. A degenerate optimal basis graph G is a subgraph of G induced by all optimal bases ata degenerate optimal vertex x. In this paper, several conditions for the characterization of G“are presented. 相似文献
17.
Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect. 相似文献
18.
19.
The object of this paper is to show that every maximal planar graph is recognizable from its family of vertex-deleted subgraphs. 相似文献
20.
Federico Ardila 《Annals of Combinatorics》2005,8(4):379-389
Given a matroid M on the ground set E, the Bergman fan
or space of M-ultrametrics, is a polyhedral complex in
which arises in several different areas, such as tropical algebraic geometry, dynamical systems, and phylogenetics. Motivated by the phylogenetic situation, we study the following problem: Given a point in
we wish to find an M-ultrametric which is closest to it in the
-metric. The solution to this problem follows easily from the existence of the subdominant M-ultrametric: a componentwise maximum M-ultrametric which is componentwise smaller than . A procedure for computing it is given, which brings together the points of view of matroid theory and tropical geometry. When the matroid in question is the graphical matroid of the complete graph Kn, the Bergman fan
parameterizes the equidistant phylogenetic trees with n leaves. In this case, our results provide a conceptual explanation for Chepoi and Fichets method for computing the tree that most closely matches measured data.Received August 12, 2004 相似文献