Number of induced matchings of graphs. (English) Zbl 1464.05305
Summary: A matching \(M\) of a graph \(G\) is an induced matching if no two edges in \(M\) are joined by an edge of \(G\). Let \(iz(G)\) denote the total number of induced matchings of \(G\), named \(iz\)-index. It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence. In this paper, we investigate the \(iz\)-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum \(iz\)-index, respectively.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C30 | Enumeration in graph theory |
References:
| [1] | Balakrishnan, H.; Barrett, C.; Kumar, V.; Marathe, M.; Thite, S., The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks, IEEE J. Sel. Areas Commun, 22, 1069-1079 (2004) · doi:10.1109/JSAC.2004.830909 |
| [2] | Cameron, K., Induced matching, Discrete Appl. Math., 24, 97-102 (1989) · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F |
| [3] | Deng, H., The largest Hosoya index of (n,n + 1)-graphs, Computers and Mathematics with Applications, 56, 2499-2506 (2008) · Zbl 1165.05321 · doi:10.1016/j.camwa.2008.05.020 |
| [4] | Didkivska, T.; St’opochkina, M., Properties of Fibonacci-Narayana numbers, In the World of Mathematics., 9, 1, 29-36 (2003) |
| [5] | Flaut, C.; Shpakivskyi, V., On generalized fibonacci quaternions and fibonacci-narayana quaternions, Discrete Appl. Math., 23, 673-688 (2013) · Zbl 1330.11009 |
| [6] | Golumbic, M.; Lewenstein, M., New results on induced matchings, Disc. Appl. Math., 101, 157-C165 (2000) · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8 |
| [7] | Gutman, I., A regularity for the boiling points of alkanes and its mathematical modeling, Z. Phys. Chem. (Leipzig), 267, 1152-1158 (1986) |
| [8] | Gutman, I.; Furtula, B.; Vidovic, D.; Hosoya, H., A concealed property of the topological index, Z. Bull. Chem. Soc. Jpn., 77, 491-496 (2004) · doi:10.1246/bcsj.77.491 |
| [9] | Gutman, I.; Yamaguchi, T.; Hosoya, H., Topological index as applied to π-electronic systems IV, On the topological factors causing non-uniform π-electronic charge distribution in non-alternant hydrocarbons, Bull. Chem. Soc. Jpn., 49, 1811-1816 (1976) · doi:10.1246/bcsj.49.1811 |
| [10] | Hosoya, H., Chemical meaning of octane number analyzed by topological indices, Croat. Chem. Acta., 75, 433-445 (2002) |
| [11] | Hosoya, H., Topological index as a sorting device for coding chemical structures, J. Chem. Doc., 12, 181-183 (1972) · doi:10.1021/c160046a010 |
| [12] | Hosoya, H.; Gao, Y., Topological index and thermodynamic properties IV, Size dependency of the structure activity correlation of alkanes, Bull. Chem. Soc. Jpn., 61, 3093-3102 (1988) · doi:10.1246/bcsj.61.3093 |
| [13] | Hosoya, H.; Hosoi, K., Topological index as applied to π-electronic systems III, Mathematical relations among various bond orders, J. Chem. Phys., 64, 1065-1073 (1976) · doi:10.1063/1.432316 |
| [14] | Hosoya, H.; Murakami, M., Topological index as applied to π-electronic systems II, Topological bond order, Bull. Chem. Soc. Jpn., 48, 3512-3517 (1975) · doi:10.1246/bcsj.48.3512 |
| [15] | Liu, Y.; Zhuang, W.; Liang, Z., Largest Hosoya Index and Smallest Merrifield-Simmons Index in Tricyclic Graphs, MATCH Commun. Math. Comput. Chem., 73, 195-224 (2015) · Zbl 1462.05092 |
| [16] | Stockmeyer, L.; Vazirani, V., NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett., 15, 14-19 (1982) · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
