In: Discrete Applied Mathematics, 2019, vol. 268, p. 102-111
The eccentricity of a vertex v in a graph G is the maximum distance between v and any other vertex of G. The diameter of a graph G is the maximum eccentricity of a vertex in G. The eccentric connectivity index of a connected graph is the sum over all vertices of the product between eccentricity and degree. Given two integers n and D with D ≤ n−1, we characterize those graphs which have...
|
In: Journal of Graph Theory, 2017, vol. 88, no. 1, p. 18-39
An induced matching 𝑀 in a graph 𝐺 is dominating if every edge not in 𝑀 shares exactly one vertex with an edge in 𝑀. The DOMINATING INDUCED MATCHING problem (also known as EFFICIENT EDGE DOMINATION) asks whether a graph 𝐺 contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In...
|
In: Journal of Heuristics, 2009, vol. 15, no. 5, p. 425-450
|
