370 KB25 KB207 KB3 KB2025Smith, Jason P.Zahedi, Emadštevilka:2, article p2.05letnik:8str. 1-10DOI:10.26493/2590-9770.1813.5ceISSN:2590-9770COBISSID_HOST:285852163URN:URN:NBN:SI:doc-H48D12J0enFakulteta za matematiko, naravoslovje in informacijske tehnologijeThe art of discrete and applied mathematicschordalcut vertexdistance preservingisometric subgraphizometrični podgrafizrezana točkaohranjanje razdaljesequentially distance preservingsimplicial vertexsimplicialna točkatetivazaporedno ohranjanje razdaljeOn distance preserving and sequentially distance preserving graphs|A graph H is an isometric subgraph of G if d_H(u,v)=d_G(u,v), for every pair u,v ? V(H). A graph is distance preserving if it has an isometric subgraph of every possible order. A graph is sequentially distance preserving if its vertices can be ordered such that deleting the first i vertices results in an isometric subgraph, for all i?1. We give an equivalent condition to sequentially distance preserving based upon simplicial orderings. Using this condition, we prove that if a graph does not contain any induced cycles of length 5 or greater, then it is sequentially distance preserving and thus distance preserving. Next we consider the distance preserving property on graphs with a cut vertex. Finally, we define a family of non-distance preserving graphs constructed from cyclesGraf H je izometričen podgraf grafa G, če je dH(u, v) =dG(u, v), za vsak par točk u, v?V(H). Graf ohranja razdaljo, če ima izometričen podgraf vsakega možnega reda. Graf zaporedno ohranja razdaljo, če se da njegove točke urediti tako, da z izbrisom prvih i točk dobimo izometričen podgraf, kar mora veljati za vse i?1. Podamo ekvivalenten pogoj za zaporedno ohranjanje razdalj, osnovan na simplicialnih ureditvah. Z uporabo tega pogoja dokažemo: če graf ne vsebuje nobenih induciranih ciklov dolžine 5 ali večjih, potem zaporedno ohranja razdalje in posledično ohranja razdalje. Obravnavamo tudi lastnost ohranjanja razdalj na grafih z rezno točko. Definiramo še družino grafov, ki ne ohranjajo razdalje, konstruirani pa so iz ciklovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije