Metrične dimenzije usmerjenih cirkulantnih grafov

Metrična dimenzija grafa predstavlja najmanjšo kardinalnost množice vozlišč, s katero se lahko enolično določi vsa ostala vozlišča grafa glede na njihove razdalje do izbranih vozlišč. V članku je obravnavana metrična dimenzija v smeri urinega kazalca usmerjenih cirkulantnih grafov \(C(n,d)\). Najprej je predstavljen celoštevilski linearni program za izračun metrične dimenzije poljubnega usmerjenega grafa ter analiza njegove časovne zahtevnosti. Nato so z računalniškimi eksperimenti izračunane metrične dimenzije grafov \(C(n,d)\) za \(n \leq 40\) in na podlagi dobljenih rezultatov je oblikovanih več domnev in splošnih lastnosti. Dokazana je formula za razdaljo med poljubnima vozliščema in izraz za premer grafa \(C(n,d)\) ter izpeljane so splošne zgornje in spodnje meje za metrično dimenzijo. Poleg tega so podane natančne vrednosti metrične dimenzije za nekatere posebne družine grafov, med drugim za \(C(n,1)\), \(C(n,2)\), \(C(n,n-1)\) in \(C(n,n-2)\). Rezultati nakazujejo tesno povezavo med parametroma \(n\) in \(d\) ter odpirajo več vprašanj za nadaljnje raziskovanje metrične dimenzije usmerjenih cirkulantnih grafov.

Metric dimension of directed circulant graphs

The metric dimension of a graph is the minimum cardinality of a set of vertices that uniquely determines all other vertices of the graph by their distances to the selected vertices. In this paper, the metric dimension of clockwise-oriented circulant graphs \(C(n,d)\) is studied. First, an integer linear programming formulation for computing the metric dimension of an arbitrary directed graph is presented, and its computational complexity is analyzed. Using computational experiments, the metric dimensions of graphs \(C(n,d)\) for \(n \leq 40\) are then determined, and several conjectures and general properties are formulated based on the obtained results. A formula for the distance between arbitrary vertices and an expression for the diameter of the graph \(C(n,d)\) are derived, and general upper and lower bounds for its metric dimension are established. Furthermore, exact values of the metric dimension are provided for several special families of graphs, including \(C(n,1)\), \(C(n,2)\), \(C(n,n-1)\), and \(C(n,n-2)\). The results indicate a strong relationship between the parameters \(n\) and \(d\) and open several directions for further research on the metric dimension of directed circulant graphs.