شبهه ترنسورسالها درمربعات لاتین و k-احاطه گری در گرافها

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشیار، دانشکده ریاضی، دانشگاه محقق اردبیلی، اردبیل، ایران

2 دکتر، دانشکده ریاضی، دانشگاه هوکایدو، ساپورو، ژاپن

چکیده

یک مربع لاتین از مرتبه $n$ یک آرایه $n xn$ از $n$ شئ مختلف است که در هیچ سطر وستون آن عضو تکراری موجود نباشد. در این مقاله به‌معرفی گراف‌های مربع لاتین پرداخته و سپس مسئله‌‌ی احاطه‌گری را در این گراف‌ها را بررسی کرده و هم‌چنین ارتباط این مسئله‌ با مفاهیم تعریف شده در مربع‌های لاتین مثل مربع‌های متعامد و $k$- ترانسورسال‌ها را مطالعه خواهیم نمود.

مسئله‌ احاطه‌گری گراف مربع لاتین، تا آن‌جائی که اطلاع داریم، به‌صورت کلی تا زمان نوشتن این مقاله در جایی مطالعه نشده است. اگرچه حالت خاصی از این مسئله‌، مطالعه‌ی مربع‌های لاتین دارای متعامد، یک مسئله‌ معروف در ترکیبیات است.

کلیدواژه‌ها


عنوان مقاله [English]

Quasi-transversals in Latin squares and k-domination in graphs

نویسندگان [English]

  • Adel P. Kazemi 1
  • Behnaz Pahlavsay 2
1 Associate Professor, Faculty of Mathematics, Mohaghegh Ardabili University, Ardabil, Iran
2 Ph.D., Faculty of Mathematics, Hokkaido University, Sapporo, Japan
چکیده [English]

In this paper, we first present the relation between a transversal in a Latin square with some concepts in its Latin square graph, and give an equivalent condition for a Latin square has an orthogonal mate. The most famous open problem involving Combinatorics is to find maximum number of disjoint transversals in a Latin square. So finding some family of decomposible Latin squares into disjoint transversals is our next aim. In the next section, we give an equivalent statement of a conjecture which has been attributed to Brualdi, Stein and Ryser by the concept of quasi-transversal. Finally, we prove the truth of the Rodney's conjecture for a family of graphs.

کلیدواژه‌ها [English]

  • Latin square
  • transversal
  • quasi-transversal
  • $k$-domination number

Smiley face

[1]    H. Ning, F. Farha, Z. N. Mohammad & M. Daneshmand, "A Survey and Tutorial on “Connection Exploding Meets Efficient Communication” in the Internet of Things," in IEEE Internet of Things Journal, vol. 7, no. 11, pp. 10733-10744, Nov. 2020.
[2]    V. Hassija, V. Chamola, V. Saxena, D. Jain, P. Goyal & B. Sikdar, "A Survey on IoT Security: Application Areas, Security Threats, and Solution Architectures," in IEEE Access, vol. 7, pp. 82721-82743, 2019.
[3]    C. H. Liao, H. -H. Shuai & L. C. Wang, "Eavesdropping prevention for heterogeneous Internet of Things systems," 2018 15th IEEE Annual Consumer Communications & Networking Conference (CCNC), pp. 1-2, 2018.
[4]    S. A. Mohajeran & G. A. Hodtani, "Power Allocation for Wireless Sensor Networks in the Presence of Non-Gaussian Noise and Hardware Impairments Using Distance-Related Bounds," in IEEE Sensors Letters, vol. 5, no. 4, pp. 1-4, April 2021.
[5]    G. Ding, X. Gao, Z. Xue, Y. Wu & Q. Shi, ”Massive MIMO for Distributed Detection With Transceiver Impairments,” in IEEE Transactions on Vehicular Technology, vol. 67, no. 1, pp. 604-617, Jan. 2018.
[6]    C. Mollén, U. Gustavsson, T. Eriksson & E. G. Larsson, "Impact of Spatial Filtering on Distortion From Low-Noise Amplifiers in Massive MIMO Base Stations," in IEEE Transactions on Communications, vol. 66, no. 12, pp. 6050-6067, Dec. 2018
[7]    P. Williams, P. Rojas & M. Bayoumi, "Security Taxonomy in IoT – A Survey," 2019 IEEE 62nd International Midwest Symposium on Circuits and Systems (MWSCAS), pp. 560-565, 2019.
[8]    N. Sklavos & I. D. Zaharakis, "Cryptography and Security in Internet of Things (IoTs): Models, Schemes, and Implementations," 2016 8th IFIP International Conference on New Technologies, Mobility and Security (NTMS), pp. 1-2, 2016.
[9]    J. Zhang, S. Rajendran, Z. Sun, R. Woods & L. Hanzo, "Physical Layer Security for the Internet of Things: Authentication and Key Generation," in IEEE Wireless Communications, vol. 26, no. 5, pp. 92-98, October 2019.
[10]  Y. Chen, W. Li & H. Shu, "Wireless physical-layer security with multiple receivers and eavesdroppers: Outage probability and average secrecy capacity," 2015 IEEE 26th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 662-667, 2015.
[11]  M. Obeed & W. Mesbah, "An efficient physical layer security algorithm for two-way relay systems," 2016 IEEE Wireless Communications and Networking Conference, pp. 1-6, 2016.
[12]  A. Sonee & G. A. Hodtani, "On the Secrecy Rate Region of Multiple-Access Wiretap Channel With Noncausal Side Information," in IEEE Transactions on Information Forensics and Security, vol. 10, no. 6, pp. 1151-1166, June 2015.
[13]  Y. Liang, H. V. Poor & S. Shamai, “Information Theoretic Security, Delft,” The Netherlands: Now Publishers, 2009.
[14]  T. Cover, & J. Thomas, “Elements of Information Theory,” 2nd Edition, Wiley, (2006).
[15]  T. T. Duy & V. N. Q. Bao, "Performance analysis of cooperativebased multi-hop transmission protocols in underlay cognitive radio with hardware impairment," VNU Journal of Computer Science and Communication Engineering, vol. 31, no. 2, pp. 15-28, 2015.
[16]  J. Mo, M. Tao, & Y. Liu, "Relay placement for physical layer security: A secure connection perspective," IEEE Commun. Lett., vol. 16, no. 6, pp. 878-881, Jun. 2012.
[17]  V. N. Q. Bao, N. L. Trung, & M. Debbah, "Relay selection schemes for dual-hop networks under security constraints witb multiple eavesdroppers," IEEE Trans. Wire!' Commun., vol. 12, no. 12, pp. 6076-6085, Otc. 2013.
دوره 10، شماره 3 - شماره پیاپی 39
شماره پیاپی 39، فصلنامه پاییز
دی 1401
صفحه 67-75
  • تاریخ دریافت: 05 آبان 1400
  • تاریخ بازنگری: 23 آذر 1400
  • تاریخ پذیرش: 18 مرداد 1401
  • تاریخ انتشار: 01 دی 1401