Strongly distance-balanced graphs and graph products

Balakrishnan, Kannan; Changat, Manoj; Peterin, Iztok; Špacapan, Simon; Šparl, Primož; Subhamathi, Ajitha R.

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Strongly distance-balanced graphs and graph products
Authors:	ID Balakrishnan, Kannan (Author) ID Changat, Manoj (Author) ID Peterin, Iztok (Author) ID Špacapan, Simon (Author) ID Šparl, Primož (Author) ID Subhamathi, Ajitha R. (Author)
Files:	http://dx.doi.org/10.1016/j.ejc.2008.09.018
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
Abstract:	A graph $G$ is strongly distance-balanced if for every edge $uv$ of $G$ and every $i ge 0$ the number of vertices $x$ with $d(x,u) = d(x,v)-1 = i$ equals the number of vertices $y$ with $d(y,v) = d(y,u)-1 = i$ . It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distance-balanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity $O(mn)$ for their recognition, where m is the number of edges and $n$ the number of vertices of the graph in question, are given.
Keywords:	matematika, teorija grafov, razdaljno uravnoteženi grafi, mathematics, graph theory, distance-balanced grapha
Year of publishing:	2008
Number of pages:	str. 1048-1053
Numbering:	Vol. 30, iss. 5
PID:	20.500.12556/DKUM-51773
UDC:	519.17
ISSN on article:	0195-6698
COBISS.SI-ID:	15079769
DOI:	10.1016/j.ejc.2008.09.018
NUK URN:	URN:SI:UM:DK:E4TPOWHC
Publication date in DKUM:	10.07.2015
Views:	1939
Downloads:	99
Metadata:
Categories:	Misc.
:	BALAKRISHNAN, Kannan, CHANGAT, Manoj, PETERIN, Iztok, ŠPACAPAN, Simon, ŠPARL, Primož and SUBHAMATHI, Ajitha R., 2008, Strongly distance-balanced graphs and graph products. European journal of combinatorics [online]. 2008. Vol. 30, no. 5, p. 1048–1053. [Accessed 17 March 2025]. DOI 10.1016/j.ejc.2008.09.018. Retrieved from: http://dx.doi.org/10.1016/j.ejc.2008.09.018 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	European journal of combinatorics
Shortened title:	Eur. j. comb.
Publisher:	Academic Press
ISSN:	0195-6698
COBISS.SI-ID:	25427968

Secondary language

Language:	Unknown
Title:	Krepko razdaljno uravnoteženi grafi in produkti grafov

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back