On the ordering of graphs with respect to their matching numbers (Q1103635): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Fu Ji Zhang / rank | |||
Property / reviewed by | |||
Property / reviewed by: Johannes André / rank | |||
Property / author | |||
Property / author: Fu Ji Zhang / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Johannes André / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An introduction to matching polynomials / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the theory of the matching polynomial / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4154899 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4173371 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4748183 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184945 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3807048 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(86)90015-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2004623769 / rank | |||
Normal rank |
Latest revision as of 11:27, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the ordering of graphs with respect to their matching numbers |
scientific article |
Statements
On the ordering of graphs with respect to their matching numbers (English)
0 references
1986
0 references
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.
0 references
k-matchings
0 references
quasi-ordering relation
0 references