Simultaneous embeddings of graphs as median and antimedian subgraphs

Kannan Balakrishnan (Avtor), Boštjan Brešar (Avtor), Manoj Changat (Avtor), Sandi Klavžar (Avtor), Matjaž Kovše (Avtor), Ajitha R. Subhamathi (Avtor)

Povzetek

Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno število ▫$r \ge 2$▫ obstaja povezani graf ▫$H$▫, tako da je ▫$G$▫ antimedianski in ▫$J$▫ medianski podgraf grafa ▫$H$▫ ter da pri tem velja ▫$d_H(G,J) = r$▫. V primeru, ko sta oba ▫$G$▫ in ▫$J$▫ povezana, lahko dodatno naredimo, da sta ▫$G$▫ in ▫$J$▫ konveksna podgrafa v ▫$H$▫.

Ključne besede

matematika;teorija grafov;problemi razmeščanja;medianske množice;antimedianske množice;konveksni podgrafi;mathematics;graph theory;facility location problems;median sets;antimedian sets;convex subgraphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	2010
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15646041
ISSN:	0028-3045
Št. ogledov:	258
Št. prenosov:	28
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Hkratne vložitve grafov v obliki medianskih in antimedianskih podgrafov
Sekundarni povzetek:	The distance ▫$D_G(v)$▫ of a vertex ▫$v$▫ in an undirected graph ▫$G$▫ is the sum of the distances between ▫$v$▫ and all other vertices of ▫$G$▫. The set of vertices in ▫$G$▫ with maximum (minimum) distance is the antimedian (median) set of a graph ▫$G$▫. It is proved that for arbitrary graphs ▫$G$▫ and ▫$J$▫ and a positive integer ▫$r \ge 2$▫, there exists a connected graph ▫$H$▫, such that ▫$G$▫ is the antimedian and ▫$J$▫ the median subgraphs of ▫$H$▫, respectively, and that ▫$d_H(G,J) = r$▫. When both ▫$G$▫ and ▫$J$▫ are connected, ▫$G$▫ and ▫$J$▫ can in addition be made convex subgraphs of ▫$H$▫.
Sekundarne ključne besede:	matematika;teorija grafov;problemi razmeščanja;medianske množice;antimedianske množice;konveksni podgrafi;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 90-94
Letnik:	Vol. 56
Zvezek:	iss. 2
Čas izdaje:	2010
ID:	1475195