Matroids in terms of Cayley graphs and some related results.
Matroids over a ring
We introduce the notion of a matroid over a commutative ring , assigning to every subset of the ground set an -module according to some axioms. When is a field, we recover matroids. When , and when is a DVR, we get (structures which contain all the data of) quasi-arithmetic matroids, and valuated matroids, i.e. tropical linear spaces, respectively. More generally, whenever is a Dedekind domain, we extend all the usual properties and operations holding for matroids (e.g., duality), and...
Matroids with Sylvester Property.
Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs
Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs
Maximal buttonings of trees
A buttoning of a tree that has vertices v1, v2, . . . , vn is a closed walk that starts at v1 and travels along the shortest path in the tree to v2, and then along the shortest path to v3, and so forth, finishing with the shortest path from vn to v1. Inspired by a problem about buttoning a shirt inefficiently, we determine the maximum length of buttonings of trees
Maximal Canonical Graphs with Seven Nonzero Eigenvalues
Maximal Canonical Graphs with Three Negative Eigenvalues
Maximal facet-to-facet snakes of unit cubes.
Maximal flat antichains of minimum weight.
Maximal Graphs with Given Connectivity and Edge-Connectivity
Maximal graphs with respect to hereditary properties
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P...
Maximal hypergraphs with respect to the bounded cost hereditary property
The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.
Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles.
Maximal k-independent sets in graphs
A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and and between iₖ(G) and for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.
Maximal nests of subspaces, the matrix Bruhat decomposition, and the marriage theorem---with an application to graph coloring.
Maximal nontraceable graphs with toughness less than one.
Maximal pentagonal packings.
Maximal projective degrees for strict partitions.
Maximal sets of numbers not containing k+1 pairwise coprime integers
Maximal sum-free sets and block designs