Exploring Novel Graphs with Diverse Properties for Real-World Applications

Articles in Press

Document Type : Research Article

Authors

Department of Algorithms and Computation, School of Engineering Sciences, College of Engineering, University of Tehran, 16 Azar, Tehran, 1417614411, Tehran, Iran

Abstract

Graphs are versatile mathematical models used to solve a wide range of practical and mathematical problems. However, meeting the specific requirements of applications, such as wireless sensor network key pre-distribution, small-world complex network modeling, and Ramsey theorems, necessitates graph designs with tailored characteristics and a combination of desirable properties. These properties include minimum vulnerability, minimum diameter, regularity, Hamiltonian connectivity, and minimal complete subgraph representation. Incorporating multiple such features into a single graph presents a challenge due to conflicting properties and the exponential difficulty of achieving a desired combination. To address this challenge and provide more realistic representations, we propose an algorithm for generating a novel class of graphs called Tight graphs. We conduct a thorough investigation into the properties of these graphs and demonstrate their potential applicability in diverse domains, including wireless sensor network key pre-distribution, small-world complex network models, and improved lower bounds for Ramsey numbers. Our algorithm enables the design of graphs that strike a balance between desirable properties, catering to the specific requirements of various applications.

Keywords

Main Subjects

Scientia Iranica

Articles in Press, Accepted Manuscript
Available Online from 11 May 2025

Files

History

  • Receive Date: 08 July 2024
  • Revise Date: 13 December 2024
  • Accept Date: 06 April 2025

Share

How to cite

Statistics