BRAIN. Broad Research in Artificial Intelligence and Neuroscience,
ISSN 2067-3957, Volume 1, July 2010,
Special Issue on Complexity in Sciences and Artificial Intelligence,
Eds. B. Iantovics, D. Rǎdoiu, M. Mǎruşteri and M. Dehmer

OPTIMIZATION PROBLEMS ON THRESHOLD GRAPHS

Mihai Talmaciu and Elena Nechita

Abstract. During the last three decades, different types of decompo-
sitions have been processed in the field of graph theory. Among these we
mention: decompositions based on the additivity of some characteristics of the
graph, decompositions where the adjacency law between the subsets of the par-
tition is known, decompositions where the subgraph induced by every subset
of the partition must have predeterminate properties, as well as combinations
of such decompositions.

In this paper we characterize threshold graphs using the weakly decom-
position, determine: density and stability number, Wiener index and Wiener
polynomial for threshold graphs.

Keywords: Threshold graph, weakly decomposition, Wiener index, Wiener
polynomial.

2000 Mathematics Subject Classification: 05C99, 68R10.

61



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

1.Preliminary results

1.1. Weakly decomposition
At first, we recall the notions of weakly component and weakly decompo-

sition.
Definition 1. ([5], [18], [19]) A set A ⊂ V (G) is called a weakly set of the

graph G if NG(A) 6= V (G) − A and G(A) is connected. If A is a weakly set,
maximal with respect to set inclusion, then G(A) is called a weakly component.
For simplicity, the weakly component G(A) will be denoted with A. If A is
a weakly set, then the partition {A, N (A), V − A ∪ N (A)} is called a weakly
decomposition of G with respect to A.

Below we remind a characterization of the weakly decomposition of a graph.
The name of ”weakly component” is justified by the following result.
Theorem 1. ([6], [18], [19]) Every connected and non-complete graph

G = (V, E) admits a weakly component A such that G(V − A) = G(N (A)) +
G(N (A)).

Let A ⊂ V . Then A is a weakly component of G if and only if G(A) is
connected and N (A) ∼ N (A).

The next result, that follows from Theorem 1, ensures the existence of a
weakly decomposition in a connected and non-complete graph.

Corollary 1. If G = (V, E) is a connected and non-complete graph, then
V admits a weakly decomposition (A, B, C), such that G(A) is a weakly com-
ponent and G(V − A) = G(B) + G(C).

Theorem 1 provides an O(n + m) algorithm for building a weakly decom-
position for a non-complete and connected graph.

Algorithm for the weakly decomposition of a graph ([18])
Input: A connected graph with at least two nonadjacent vertices, G = (V, E).
Output: A partition V = (A, N, R) such that G(A) is connected, N = N (A),
A 6∼ R = N (A).
begin

A := any set of vertices such that
A ∪ N (A) 6= V
N := N (A)
R := V − A ∪ N (A)
while (∃n ∈ N , ∃r ∈ R such that nr 6∈ E ) do

begin
A := A ∪ {n}

62



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

N := (N − {n}) ∪ (N (n) ∩ R)
R := R − (N (n) ∩ R)

end
end

1.2. Threshold graphs
In this subsection we remind some results on threshold graphs.
A graph G is called threshold graph if NG(x) ⊆ NG[y] or NG(y) ⊆ NG[x]

for any pair of vertices x and y in G.
Threshold graphs were first introduced by Chvátal and Hammer ([3]).
In [16], Ortiz and Villanueva-Ilufi give a structural characterization of

threshold graphs for solving the following two difficult problems: enumera-
tion of all maximal independent sets and the chromatic index problem.

Theorem 2. ([3]) A graph G is a threshold graph if and only if G does
not contain a C4, C4, P4 as an induced subgraph.

Chvátal and Hammer also showed that threshold graphs can be recognizing
in O(n2) time.

In [1], Babel showed that if G is a threshold graph then the algorithms that
determine ω(G), χ(G), α(G) and θ(G) are O(n + m) time.

Theorem 3. ([3]) A graph G is a threshold graph if and only if G is a
cograph and G is a split graph.

In [4] (as well as in [10] and [14]) linear algorithms for recognizing a cograph
can be found. Hammer and Simeone [11]) give an O(n + m) algorithm for
recognizing a split graph. Therefore, an algorithm that recognizes a threshold
graph is O(n(n + m)).

In [15] a linear algorithm for recognizing a threshold graph can be found.

2.New results on threshold graphs

2.1. Characterization of a threshold graph using the weakly decom-
position

In this paragraph we give a new characterization of threshold graphs using
the weakly decomposition. Also, we determine the stability number and the
clique number for threshold graphs.

Theorem 4. Let G=(V,E) be a connected graph with at least two nonad-
jacent vertices and (A,N,R) a weakly decomposition, with A the weakly com-
ponent. G is a threshold graph if and only if:
i) A ∼ N ∼ R;

63



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

ii) dG(n) = |V | − 1, dG(r) = |N|, ∀n ∈ N , ∀r ∈ R;
iii) G(A) is threshold graph.

The above results lead to a recognition algorithm with the total execution
time O(n(n + m)).

2.2. Determination of clique number and stability number for a
threshold graph

The threshold graphs is a graph class of bounded clique-width ([2]).
Theorem 5. Let G=(V,E) be connected with at least two non-adjacent

vertices and (A,N,R) a weakly decomposition with A the weakly component. If
G is a threshold graph then

α(G) = α(G(A)) + |R| and ω(G) = ω(G(A)) + |N|.
As a consequence of the above theorem, we give an algorithm that leads

to a stable set of maximal cardinal and to a clique of maximal cardinal in a
threshold graph.

Input: A threshold, connected graph with at least two nonadjacent vertices,
G = (V, E)

Output: Determination of α(G) and ω(G)
begin

S = ∅; Q = ∅; s := 0; q := 0; i := 1; Gi := G;
while |V (Gi)| ≥ 4 do

Determine a weakly decomposition (Ai, Ni, Ri) of Gi, with Ri stable,
Ni clique and G(Ai) threshold
if (Gi is complete) then

S := S ∪ {v}, s := s + 1, ∀v ∈ V (Gi);
Q := Q ∪ V (Gi), q := q + |V (Gi)|

else
S := S ∪ Ri, s := s + |Ri|;
Q := Q ∪ Ni, q := q + |Ni|;
i := i + 1;
H := Gi;

α(G) := s + α(H);
ω(G) := q + ω(H)

end
Remark 1. The most time consuming operation inside the while loop is

the determination of the decomposition (A, N, R), namely O(n + m). As the

64



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

while body executes at most n times, it follows that the total execution time
is O(n(n + m)).

The characterization theorem of threshold graphs leads to the following
result that is useful in the next section.

Corollary 2. Let G=(V,E) be connected with at least two non-adjacent
vertices and (A,N,R) a weakly decomposition with A the weakly component. If
G is a threshold graph then if after k steps in the weakly decomposition algo-
rithm of G we get |Ak| ≤ 3 then Ak ' K3 or Ak ' K2 or Ak ' K1.

3.Some Applications in Optimization Problems

In this section we point some applications of threshold graphs in optimization
problems.

Facility location analysis deals with the problem of finding optimal loca-
tions for one or more facilities in a given environment [13]. Location problems
are classical optimization problems with many applications in industry and
economy. The spatial location of the facilities often takes place in the con-
text of a given transportation, communication, or transmission system. A first
paradigme for location is based on the minimization of transportation cost.

According to their objective function, we can consider two types of loca-
tion problems. The first type consists of those problems that use a minimax
criterion. For example, if we want to determine the location of a hospital the
main objective is to find a site that minimizes the maximum response time
between the hospital and site of a possible emergency. More generally, the
aim of the first problem type is to determine a location that minimizes the
maximum distance to any other location in the network. The second type of
location problems optimizes a ”minimum of a sum” criterion, which is used in
determining the location for a service facility like a shopping mall, for which
we try to minimize the total travel time. The following centrality indices are
defined in [13].

The eccentricity of a vertex u is eG(u) = max{d(u, v)|v ∈ V }.
The radius is r(G) = min{eG(u)|u ∈ V }.
The center of a graph G is C(G) = {u ∈ V |r(G) = eG(u)}.
We consider the second type of location problems. Suppose we want to

place a service facility such that the total distance to all customers in the
region is minimal. The problem of finding an appropriate location can be
solved by computing the set of vertices with minimum total distance.

65



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

We denote the sum of the distances from a vertex u to any other vertex in
a graph G=(V,E) as the total distance s(u) =

∑
v∈V d(u, v). If the minimum

total distance of G is denoted by s(G) = min{s(u)|u ∈ V }, the median M(G)
of G is given by M(G) = {u ∈ V |s(G) = s(u)} .

The Wiener index was introduced in 1947 by Horold Wiener ([20]) and is
defined as the sum of distance between all pairs of vertices in G:

W (G) =
∑

u,v∈V dG(u, v).

We wish to point out that the theoretical framework is especially well elabo-
rated for the Wiener index of trees ([7]).

The distance-counting polynomial was introduced [12] as:

H(G, x) =
∑

k d(G, k)x
k,

with d(G, 0) = |V (G)| and d(G, 1) = |E(G)|, where d(G, k) is the number of
pair vertices lying at distance k to each other. This polynomial was called
Wiener, by its author Hosoya, in the more recent literature [9], [17].

Our result concerning the center of a threshold graph is the following.
Theorem 6. Let G=(V,E) be a connected graph with at least two nonad-

jacent vertices. If G is threshold and if after k steps in the algorithm weakly
decomposition of G we get |Ak| ≤ 3 , then the center and the median are equal
to N , the radius is 1, while the excentricity is 1 for the vertices in N and 2
for the others. Also

H(G, x) = [ 1
2
(α(G) − 1)2 + |Ak|(α(G) − 1)]x2 + |E(G)|x + |V (G)| and

W (G) = |E(G)| + (α(G) − 1)2 + 2|Ak|(α(G) − 1).

References

[1]L. Babel, On the P4-structure of graphs, Habilitationsschrift, TU Munchen
1997.

[2]A. Brandtstead, F.F. Dragan, H.O. Le, R. Mosca, New graph classes of
bounded clique-width, WG2002, Lecture Notes in Compute Science 2573, 57-67
(2002), ZMath 1022.68090

[3]V. Chváatal and P.L. Hammer, Agregation on Inequalities in Integer
Programming, Ann. Disc. Maths. 1977. I. 145-162.

66



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

[4]D.G. Corneil, Y. Perl and L.K. Stewart Burlinham, A Linear Recognition
Algorithm for Cographs, SIAM J. Computing 14 (4), 1985, pp. 926-934.

[5]C. Croitoru, M. Talmaciu, A new graph search algorithm and some ap-
plications, presented at ROSYCS 2000, Univ. ”Al.I.Cuza” Iaşi,2000.

[6]C. Croitoru, E. Olaru, M. Talmaciu, Confidentially connected graphs,
The annals of the University ”Dunarea de Jos” of Galati, Suppliment to Tome
XVIII (XXII) 2000, Proceedings of the international conference ”The risk in
contemporany economy”.

[7] A.A.Dobrynin, R.Entringer and I. Gutman, Wiener index of trees: the-
ory and applications, Acta Appl. Math. 66(2001), 211-249.

[8] M.C.Golumbic, Algorithmic graph theory and perfect graph. Academic
Press, New York, 1980.

[9] I. Gutman, S. Klavzar, M. Petkovsek and P. Zigert, On Hosoya poly-
nomials of benzenoid graphs. MATCH Commun. Math. Comput. Che.
43(2001), 49-66.

[10] M.Habib and C.Paul, A simple linear time algorithm for cograph recog-
nition, Discrete Applied Mathematics, 145:183-197, 2005.

[11] P.L.Hammer and B.Simeone, The splitance of a graph, Combinatorica
1(1981), 275-284.

[12] H.Hosoya, On some couting polynomials in chemistry. Discrete Appl.
Math. 19(1988), 239-257.

[13] D. Koschutzki, K. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl
and O. Zlotowski, ”Centrality Indices”, Lecture Notes in Computer Sciences,
Springer Berlin / Heidelberg, Network Analysis, 16-61, 2005.

[14] R.Lin and S.Olariu, An Nc Recognition Algorithm for Cograph, Journal
of Parallel and Distributed Computing, 13, 76-91 (1991).

[15] N.V.R.Mahadev, U.N.Peled, Threshold graph and related topics, An-
nals of Discrete Mathematics, vol. 56, Elsevier, North-Holland, Amsterdam,
1995.

[16] C.Ortiz Z, M.Villanueva-Ilufi, Difficult Problems in Threshold Graphs,
Electronic Notes in Discrete Mathematics 18(2004) 187-192.

[17] D. Stevanovic, Hosoya polynomial of composite graphs. Discrete Math.,
235 (2001), 237-244.

[18]M. Talmaciu, Decomposition Problems in the Graph Theory with Ap-
plications in Combinatorial Optimization - Ph. D. Thesis, University ”Al. I.
Cuza” Iasi, Romania, 2002.

[19]M. Talmaciu, E. Nechita, Recognition Algorithm for diamond-free graphs,

67



M.Talmaciu and E.Nechita - Optimization problems on threshold graphs

Informatica, 2007, Vol. 18, No. 3, 457-462, ISSN 0868-4952.
[20]H. Wiener, Structural determination of paraffin boiling points, J. Am.

Chem. Soc. 69 (1947), 17-20.

Mihai Talmaciu and Elena Nechita
Department of Mathematics and Informatics
”Vasile Alecsandri” University of Bacău
Calea Marasesti, 157, Postal code 600115, Bacău, Romania
e-mail:mtalmaciu@ub.ro, enechita@ub.ro

68