Matroid basis graphs. II

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.     

Hadamard graphs. I

In order to provide an algebraic graph theoretic background for Hadamard matrices and designs Hadamard graphs are introduced and their spectra are determined.     

Precoloring extension. I. Interval graphs

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.     

Intervals in matroid basis graphs

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.     

双圈拟阵

Sim■es Pereira于1992年提出双圈拟阵.本文讨论了(i)双圈拟阵及其秩函数;(ii)次模函数在双圈拟阵中的应用;(iii)双圈拟阵B(G)的横贯拟阵.主要结果:1°由圈矩阵Bf=[I,Bf12]和圈秩的概念,推出M(f0)为双圈拟阵;2°证明了双圈拟阵B(G)等于由子集族{Av∶v∈V(G)},e与v在G中相关联}所确定的横贯拟阵;3°用不同于Matthews(1977)的方法证明了(iii).     

联图的圈基

MacLane于1937年给出了圈基方面的重要定理: 图G是平面图, 当且仅当图G有2-重基. 连通图G_1和G_2的联图G_1\vee G_2指的是在它们的不交并G_1\bigcup G_2上添加边集(u,v)|u\in V(G_1), v\in V(G_2). 对G_1和G_2的联图G_1\vee G_2的圈基重数进行了研究, 得到了一个上界, 改进了Zare的结果. 并在此基础之上, 进一步得到特殊联图C_m\vee C_n的圈基重数的一个上界.     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

Matroid intersection algorithms

LetM ₁ = (E, 9₁),M ₂ = (E, 9₂) be two matroids over the same set of elementsE, and with families of independent sets 9₁, 9₂. A setI 9₁ 9₂ is said to be anintersection of the matroidsM ₁,M ₂. An important problem of combinatorial optimization is that of finding an optimal intersection ofM ₁,M ₂. 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 ₁,M ₂. 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.     

Spectra of graphs and fractal dimensions. I

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.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

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 K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,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.     

线性规划中的退化最优基图

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.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

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.     

The reconstruction of maximal planar graphs. I. Recognition

The object of this paper is to show that every maximal planar graph is recognizable from its family of vertex-deleted subgraphs.     

Subdominant Matroid Ultrametrics

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 K_n, 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