New math model reveals hidden paths in complex networks
Researchers have identified a mathematical property that guarantees networks—whether computer systems, supply chains, or social platforms—contain diverse routing options between any two points. The finding could help engineers design more resilient infrastructure and improve network optimization algorithms used across telecommunications and logistics.
Originaltitel: Some panconnected and pancyclic properties of graphs with a local ore-type condition
<p>Asratian and Khachatrian proved that a connected graph<em>G</em> of order at least 3 is hamiltonian if<em>d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)|</em> for any path<em>uwv</em> with<em>uv ∉ E(G)</em>, where<em>N(x)</em> is the neighborhood of a vertex<em>x.</em></p><p>We prove that a graph<em>G</em> with this condition, which is not complete bipartite, has the following properties:</p><ol><li>a) For each pair of vertices<em>x, y</em> with distance<em>d(x, y)</em> ≥ 3 and for each integer<em>n, d(x, y) ≤ n ≤ |V(G)|</em> − 1, there is an<em>x − y</em> path of length<em>n.</em> </li><li>(b)For each edge<em>e</em> which does not lie on a triangle and for each<em>n, 4 ≤ n ≤ |V(G)|</em>, there is a cycle of length<em>n</em> containing<em>e.</em> </li><li>(c)Each vertex of<em>G</em> lies on a cycle of every length from 4 to |<em>V(G)</em>|. </li></ol><p>This implies that<em>G</em> is vertex pancyclic if and only if each vertex of<em>G</em> lies on a triangle.</p>