ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH

Document Type : Research Paper

Authors

1 School of Information and Engineering, Wuchang University of Technology, Wuhan, 430223, China

2 School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, 430073, China

3 Institute of Uncertain Systems, Huanggang Normal University, Huang- gang, 438000, China

Abstract

Uncertain graphs are employed to describe graph models with indeterministic
information that produced by human beings. This paper aims to study the
maximum matching problem in uncertain graphs.
The number of edges of a maximum matching in a graph is called matching number
of the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable.
Different from that in a deterministic graph, it is more meaningful to investigate the uncertain measure that an uncertain graph is $k$-edge matching (i.e., the matching number is greater than or equal to $k$).
We first study the properties of the matching number of an uncertain graph, and then give a fundamental formula for calculating the uncertain measure. We further prove that the fundamental formula can be transformed
into a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form.
Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm.

Keywords

References

[1] B. Bollobas, Degree sequences of random graphs, Discrete Mathematics, 33 (1981), 1-19.
[2] J. Bondy and U. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
[3] L. Clark, The strong matching number of a random graph, Canadian Journal of Mathematics,
24 (2001), 47-57.
[4] J. Edmonds, Paths, trees, and owers, Canadian Journal of Mathematics, 17(3) (1965),
449-467.
[5] A. EI Maftouhi and L. M. Gordones, The maximum size of a strong matching in a random
graph, Australasian Journal of Combinatorics, 10 (1994), 97-104.
[6] A. EI Maftouhi, The minimum size of a maximal strong matching in a random graph, Australasian
Journal of Combinatorics, 12 (1995), 77-80.
[7] P. Erdos and A. Renyi, On random graph I, Publicationes Mathematicae Debrecen, 6 (1959),
290-297.
[8] P. Erdos and A. Renyi, On the strength of connectedness of a random graph, Acta Mathematica
Hungarica, 12(1-2) (1964), 261-267.
[9] H. N. Gabow, An efficient implementation of Edmonds' algorithm for maximum matching
on graphs, The Journal of the ACM, 23(2) (1976), 221-234.
[10] X. Gao, Cycle index of uncertain graph, Information: An International Interdisciplinary
Journal, 16(2(A)) (2013), 1131-1138.
[11] X. Gao, Regularity index of uncertain graph, Journal of Intelligent and Fuzzy Systems, 27(4)
(2014), 1671-1678.
[12] X. Gao and Y. Gao, Connectedness index of uncertain graphs, International Journal of Uncertainty,
Fuzziness and Knowledge-Based Systems, 21(1) (2013), 127-137.
[13] Y. Gao, Shortest path problem with uncertain arc lengths, Computers and Mathematics with
Applications, 62(6) (2011), 2591-2600.
[14] Y. Gao, L. Yang, S. Li and S. Kar, On distribution function of the diameter in uncertain
graph, Information Sciences, 296 (2015), 61-74.
[15] Y. Gao and Z. Qin, On computing the edge-connectivity of an uncertain graph, IEEE Transactions
on Fuzzy Systems, 24(4) (2015), 981-991.
[16] A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, Cambridge, 1985.
[17] E. Gilbert, Random graphs, Annals of Mathematical Statistics, 30(4) (1959), 1141-1144.
[18] S. Han, Z. Peng and S. Wang, The maximum ow problem of uncertain network, Information
Sciences, 265 (2014), 167-175.
[19] A. N. Kolmogorov, Grundbegriffe der Wahrscheinlichkeitsrechnung, Julius Springer, Berlin,
1933.
[20] B. Liu, Uncertainty Theory, second ed., Springer-Verlag, Berlin, 2007.
[21] B. Liu, Some research problems in uncertainty theory, Journal of Uncertain Systems, 3(1)
(2009), 3-10.
[22] B. Liu, Uncertainty theory: A Branch of Mathematics for Modeling Human Uncertainty,
Springer-Verlag, Berlin, 2010.
[23] B. Liu, Why is there a need for uncertainty theory? Journal of Uncertain Systems, 6(1)
(2012), 3-10.
[24] B. Liu, Uncertainty Theory, fourth ed., Springer-Verlag, Berlin, 2015.
[25] B. Liu and K. Yao, Uncertain multilevel programming: Algorithm and applications, Computers
& Industrial Engineering, 89 (2015), 235-240.
[26] H. M. Mahmoud, R. T. Smythe and J. Szymanski, On the structure of random plane-oriented
recursive trees and their branches, Random Structures & Algorithm, 4(2) (1993), 151-176.
[27] S. Mathew and M. S. Sunitha, Node connectivity and arc connectivity of a fuzzy graph,
Information Sciences. 180(4) (2010), 519-531.
[28] J. N. Mordeson and P. S. Nair, Fuzzy Graphs and Fuzzy Fypergraphs, Physica-Verlag, Heidelberg,
2000.
[29] A. Rosenfeld, Fuzzy Graphs, In: L. A. Zadeh, K. S. Fu and M. Shimura (Eds.), Fuzzy sets
and their applications to cognitive and decision processes. Academic Press, New York, 1975.
[30] S. Samanta and M. Pal, Fuzzy k-competition graphs and p-competition fuzzy graphs, Fuzzy
Information and Engineering, 5(2) (2013), 191-204.
[31] Y. Sheng and K. Yao, Fixed charge transportation problem in uncertain environment, Industrial
Engineering and Management Systems, 11(2) (2012), 183-187.
[32] Y. Sheng and K. Yao, A transportation model with uncertain costs and demands, Information:
An International Interdisciplinary Journal, 15(8) (2012), 3179-3186.
[33] M. S. Sunitha and S. Mathew, Fuzzy graph theory: A survey, Annals of Pure and Applied
Mathematics, 4(1) (2013), 92-110.
[34] X. Wu, R. Zhao and W. Tang, Optimal contracts for the agency problem with multiple
uncertain information, Knowledge-Based Systems, 59 (2014), 161-172.
[35] K. Yao, No-arbitrage determinant theorems on mean-reverting stock model in uncertain mar-
ket, Knowledge-Based Systems, 35 (2012), 259-263.
[36] R. T. Yeh and S. Y. Bang, Fuzzy Relations, Fuzzy Graphs and Their Applications to Clus-
tering Analysis, In: L. A. Zadeh, K. S. Fu and M. Shimura (Eds.), Fuzzy sets and their
applications to cognitive and decision processes. Academic Press, New York, 1975.
[37] L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338-353.
[38] B. Zhang and J. Peng, Uncertain programming model for Chinese postman problem with
uncertain weights, Industrial Engineering and Management Systems, 11(1) (2012), 18-25.
[39] B. Zhang and J. Peng, Euler index in uncertain graph, Applied Mathematics and Computation,
218(20) (2012), 10279-10288.
[40] B. Zhang and J. Peng, Matching index of an uncertain graph: Concept and algorithm, Applied
and Computational Mathematics, 12(3) (2013), 381-391.
[41] J. Zhou, L. Chen and K. Wang, Path optimality conditions for minimum spanning tree
problem with uncertain edge weights, International Journal of Uncertainty, Fuzziness and
Knowledge-Based Systems, 23(1) (2015), 49-71.
Iranian Journal of Fuzzy Systems
Volume 15, Issue 2
March and April 2018
Pages 89-108

Files

Share

How to cite

Statistics