On the ordering of graphs with respect to their matching numbers
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.
- scientific article; zbMATH DE number 4053878
- On the ordering of a class of graphs with respect to their matching numbers
- On ordering of complements of graphs with respect to matching numbers
- On ordering of complements of graphs with respect to matching numbers
- Graphs that contain multiply transitive matchings
- An introduction to matching polynomials
- scientific article; zbMATH DE number 4074878 (Why is no real title available?)
- scientific article; zbMATH DE number 3583866 (Why is no real title available?)
- scientific article; zbMATH DE number 3608048 (Why is no real title available?)
- scientific article; zbMATH DE number 3803493 (Why is no real title available?)
- scientific article; zbMATH DE number 3893246 (Why is no real title available?)
- On the theory of the matching polynomial
- On extremal unicyclic molecular graphs with maximal Hosoya index
- On the matching polynomial of subdivision graphs
- Ordering of the trees with a perfect matching by minimal energies
- On acyclic conjugated molecules with minimal energies
- On ordering of complements of graphs with respect to matching numbers
- The Merrifield-Simmons index and Hosoya index of C(n, k, ) graphs
- Ordering of Hosoya indices for unicyclic Hückel graphs
- Matching orderable and separable hypergraphs
- Coulson integral formula for the vertex energy of a graph
- On the permanental sum of graphs
- Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching
- Extremal polyomino chains on k-matchings and k-independent sets
- The largest Hosoya index of (n,n+1)-graphs
- The smallest Merrifield-Simmons index of (n,n+1)-graphs
- Extremal double hexagonal chains with respect to k-matchings and k-independent sets
- On extremal unicyclic molecular graphs with prescribed girth and minimal Hosoya index
- On the ordering of a class of graphs with respect to their matching numbers
- Some relations on the ordering of trees by minimal energies between subclasses of trees
- Results on energies for trees with a given diameter having perfect matching
- The minimum matching energy of bicyclic graphs with given girth
- Minimal energies of trees with given parameters
- On the k-matchings of the complements of bicyclic graphs
- Consecutive chemical trees with respect to energy of graph
- Extremal problems for trees with given segment sequence
- The signless Laplacian coefficients and the incidence energy of unicyclic graphs with given pendent vertices
- On maximal energy and Hosoya index of trees without perfect matching
- The largest matching roots of unicyclic graphs with a fixed matching number
- Extremal energies of trees with a given domination number
- Matchings in starlike trees
- The minimum matching energy of unicyclic graphs with fixed number of vertices of degree two
- The matching energy of a graph
- Maximum energy trees with two maximum degree vertices
- The smallest hosoya index in \((n,n+1)\)-graphs
- The proof of a conjecture concerning acyclic molecular graphs with maximal Hosoya index and diameter 4
- Ordering of Hückel trees according to minimal energies
- Ordering of the trees by minimal energies
This page was built for publication: On the ordering of graphs with respect to their matching numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103635)
