• Home
  • Browse
    • Current Issue
    • By Issue
    • By Author
    • By Subject
    • Author Index
    • Keyword Index
  • Journal Info
    • About Journal
    • Aims and Scope
    • Editorial Board
    • Editorial Staff
    • Publication Ethics
    • Indexing and Abstracting
    • Related Links
    • FAQ
    • Peer Review Process
    • News
  • Guide for Authors
  • Submit Manuscript
  • Reviewers
  • Contact Us
 
  • Login
  • Register
Home Articles List Article Information
  • Save Records
  • |
  • Printable Version
  • |
  • Recommend
  • |
  • How to cite Export to
    RIS EndNote BibTeX APA MLA Harvard Vancouver
  • |
  • Share Share
    CiteULike Mendeley Facebook Google LinkedIn Twitter Telegram
Iranian Journal of Fuzzy Systems
Articles in Press
Current Issue
Journal Archive
Volume Volume 15 (2018)
Issue Issue 2
Issue Issue 1
Volume Volume 14 (2017)
Volume Volume 13 (2016)
Volume Volume 12 (2015)
Volume Volume 11 (2014)
Volume Volume 10 (2013)
Volume Volume 9 (2012)
Volume Volume 8 (2011)
Volume Volume 7 (2010)
Volume Volume 6 (2009)
Volume Volume 5 (2008)
Volume Volume 4 (2007)
Volume Volume 3 (2006)
Volume Volume 2 (2005)
Volume Volume 1 (2004)
Li, H., Zhang, B., Peng, J. (2018). ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH. Iranian Journal of Fuzzy Systems, 15(2), 89-108. doi: 10.22111/ijfs.2018.3761
Hui Li; Bo Zhang; Jin Peng. "ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH". Iranian Journal of Fuzzy Systems, 15, 2, 2018, 89-108. doi: 10.22111/ijfs.2018.3761
Li, H., Zhang, B., Peng, J. (2018). 'ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH', Iranian Journal of Fuzzy Systems, 15(2), pp. 89-108. doi: 10.22111/ijfs.2018.3761
Li, H., Zhang, B., Peng, J. ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH. Iranian Journal of Fuzzy Systems, 2018; 15(2): 89-108. doi: 10.22111/ijfs.2018.3761

ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH

Article 7, Volume 15, Issue 2, March and April 2018, Page 89-108  XML PDF (627 K)
Document Type: Research Paper
DOI: 10.22111/ijfs.2018.3761
Authors
Hui Li1; Bo Zhang2; Jin Peng 3
1School of Information and Engineering, Wuchang University of Technology, Wuhan, 430223, China
2School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, 430073, China
3Institute 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
Uncertainty theory; Uncertain measure; Maximum matching; Matching number; Uncertain graph
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.

Statistics
Article View: 32
PDF Download: 29
Home | Glossary | News | Aims and Scope | Sitemap
Top Top

Journal Management System. Designed by sinaweb.