On the ordering of graphs with respect to their matching numbers (Q1103635): Difference between revisions

Considers graphs without loops and multiple edges. If m(G,k) is the number of k-matchings of a graph G we can define a quasi-ordering relation \(G_ 1>G_ 2\) if \(m(G_ 1,k)\geq m(G_ 2,k)\) for all k. It is already known (references are given) that several types of graph (acyclic, unicyclic, bicyclic and tricyclic) can be quasi-ordered in the sense that graphs of one of these types with a given number of vertices can be arranged in a lattice with a maximal and minimal element. In the present paper six further types of graph are defined and shown to be completely orderableiner endlichen Menge \(\Omega\) operiert auf natürliche Weise auf der Menge \(\Omega^{\{k\}}\) aller k-Teilmengen von \(\Omega\) sowie auf der Menge \(\Omega^{(k)}\) aller k-elementigen Folgen von verschiedenen Elementen von \(\Omega\) (k\(\in {\mathbb{N}})\). Seien \(G^{\{k\}}\) bzw. \(G^{(k)}\) die größten Untergruppen von Sym(\(\Omega)\), die auf \(\Omega^{\{k\}}\) bzw. \(\Omega^{(k)}\) dieselben Bahnen wie G haben. G heißt \(\{\) \(k\}\)- bzw. (k)-abgeschlossen (- closed), wenn \(G=G^{\{k\}}\) bzw. \(G=G^{(k)}\) ist. Die (k)- abgeschlossenen Gruppen wurden weitgehend von \textit{H. Wielandt} untersucht [Lect. Notes Ohio State Univ., Ohio (1969)]. Spezielle \(\{\) \(k\}\)-abgeschlossene Gruppen sind die Automorphismengruppen von Inzidenzstrukturen (\(\Omega\),B), deren Blöcke B gewisse k-Teilmengen von \(\Omega\) sind; sie sind somit k-geometrisch im Sinn von \textit{D. Betten} [Mitt. Math. Ges. Hamb. 10, 317-324 (1977; Zbl 0425.20030)]. Die Umkehrung gilt jedoch nicht. Verf. untersucht weitere Eigenschaften von \(\{\) \(k\}\)-abgeschlossenen Gruppen. Insbes. wird gezeigt: Sei \(H\leq G\leq Sym(\Omega)\), H \(\{\) \(k\}\)-abgeschlossen für ein k mit \(2\leq k\leq n-2\) und \(H_{(\Delta)}=id\) für ein \(\Delta\subseteq \Omega\) mit \(| \Delta | =r\), \(k\leq r\leq n-k\), so ist G \(\{\) \(r\}\)-abgeschlossen. Einige Anwendungen auf endliche affine und projektive Gruppen folgen.