On the Ordering of a Class of Graphs with Respect to their Matching Numbers

Based on the number of k-matching m(G,k) of a graph G, Gutman and Zhang introduced an order relation of graphs: for graphs G ₁ and G ₂, if m(G ₁,k) ≥ m(G ₂,k) for all k. The order relation has important applications in comparing Hosaya indices and energies of molecular graphs and has been widely studied. Especially, Gutman and Zhang gave complete orders of six classes of graphs with respect to the relation . In this paper, we consider a class of graphs with special structure, which is a generalization of a class of graphs studied by Gutman and Zhang. Some order relations in the class of graphs are given, and the maximum and minimum elements with respect to the order relation are determined. The new results can be applied to order some classes of graphs by their matching numbers.