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

10.24200/sci.2025.64911.9193

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