1. Introduction and Preliminary
Role assignments, introduced by Everett and Borgatti [1] , who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to individuals playing counterpart roles.
Let G be a graph with vertices representing individuals and edges representing relationships. For any vertex
, the neighborhood
of vertex v is the set of all vertices adjacent to v in G. Let
, where Z is the set of positive integers. For
, denote
and
be the subgraph of G induced by set S. For any
,
. The function r is a role assignment if
(1)
*Corresponding author.
In other words, in a role assignment, if two individuals have the same role, they are related to individuals with the same sets of roles. A k-role assignment for graph G is a role assignment r so that
. We say that G is k-role assignable if it has a k-role assignment.
Pekeč and Roberts [2] proposed a modification of the role assignment model, which would limit the number of different roles in the neighborhood of an individual. This limit could be different for different individuals or could be uniform for the network. For a group of nonnegative integers
, we define a restricted size k-role assignment r of a graph G to be a k-role assignment in which
must hold for all
. When
, we call the restricted size k-role assignment a restricted s-size k-role assignment, i.e., a k-role assignment in which
must hold for all
.
If S and T are two sets of real numbers, let the distance
be defined by
, with
if
and 0 other- wise. For a given graph G, we say the function r from
into the set of positive integers is a threshold role assignment (Roberts [3] ) if
(2)
If
, we say r is a k-threshold role assignment.
Roberts [3] also introduced an alternative definition of distance, the Hausdorff distance
,
, By convention
if
and 0 otherwise. For a given graph G, we say the function r from
into the set of positive integers is a threshold close role assignment (Roberts [3] ) if
(3)
If
, we say r is a k-threshold close role assignment. If such an assignment exists, we say G is k-threshold close role assignable.
A graph with
vertices is role primitive if it has no k-role assignment for
. Roberts and Sheng [4] studied it for a special class graphs called indifference graphs.
A good survey about role assignment is [5] . Recently, many new papers related to role assignment appeared, see [6] [7] [8] . All the graphs in the paper are simple graphs. In Section 2 we give a characterization of graphs that are k-role assignable. In Section 3 we study the restricted k-role assignable graphs and characterize the graphs that are restricted size k-role assignable or restricted s-size k-role assignable. In Section 4 we discuss the graphs that are k-threshold close role assignable. In Section 5 we discuss the maximal and minimal k-role assignable graphs.
2. k-Role Assignable Graphs
The assignment
for any vertex
is a role assignment if and only if the graph has no isolated vertices or all isolated vertices, so this describes the graphs which are 1-role assignable. The assignment where
is different for each vertex
is always a role assignment, so every graph of n vertices is n-role assignable. The other cases are not straightforward.
The 2-role assignable graphs are the first interesting class of graphs. Roberts and Sheng [9] showed that the problem of determining if G has a 2-role assign- ment is NP-complete. Sheng [10] characterized 2-role assignable indifference graphs and extended some results about indifference graphs to the broader class of triangulated graphs. For the general case, we have the following results.
Theorem 1 Let G be a graph and S a proper subset of
. If S satisfies the following properties:
•
,
•
has no isolated vertices or all isolated vertices, and
• for any
,
or
.
Then G is k-role assignable.
Proof. We give an assignment r for G by assigning each role of
to one vertex of S and k to all vertices of
. The following is to verify that r is a k-role assignment of G. In fact, we just need to check the vertices with role k. By property (3), we may assume that
and
, where
and
. For any vertex
, since
, then
So r is a k-role assignment of G in each case. The proof is complete.
Theorem 2 A graph G with at least k vertices has a k-role assignment if and only if
can be partitioned into k nonempty sets
, and the following two properties are satisfied.
•
has no isolated vertices or all isolated vertices, where
, and
• for each
, there exist
sets
, where
, such that for any
,
when
, and
when
.
Proof. Let r be a k-role assignment of graph G and
, in which
. Then it is obvious that
is partitioned into k nonempty sets
. For any
, if
, then
has no isolated vertices; if
, then all vertices of
are isolated vertices. For any
, let
, then there exist
sets
, where
, such that for any
,
when
, and
when
.
On the converse case we suppose
can be partitioned into k nonempty sets
, and G satisfies the two properties mentioned in the theorem. Let
for
. Then it is easy to check that r is a k-role assign- ment of graph G.
Roberts and Sheng [9] did some work on 2-role assignable graphs. For
, Sheng [10] have studied the indifference graphs and triangulated graphs. For
, we also have the following result.
Theorem 3 A graph G with n vertices has a
-role assignment if and only if there exist
such that
.
Proof. Let r be a
-role assignment of G. Since
, there must be two vertices x and y with the same role, i.e.,
, where
, and each of the other vertices have unique roles. Because
, if x is not adjacent to y, then
, and
is obvious; if x is adjacent to y, then
.
If there are two vertices x and y satisfying
, then let
, and the r values of the other
vertices are
respectively. It is easy to see that r is a
-role assignment of graph G.
3. Restricted k-Role Assignable Graphs
In this section we study the restricted size k-role assignment and the restricted s-size k-role assignment of a graph G. It is easy to see that any k-role assignment of graph G is a restricted k-size k-role assignment. So we may assume in the following that
and
, in which
.
Pekeč and Roberts [2] just discussed the restricted s-size k-role assignment for the special case when
, i.e., when everyone in the neighborhood of an individual should be assigned the same role. They showed that G has a restricted 1-size k-role assignment if and only if
, where
is the number of connected components of G and
is the number of connected components of G that are bipartite but not isolated vertices. In particular, a connected graph G on at least two vertices has a restricted 1-size 2-role assignment if and only if G is bipartite. For the restricted size k-role assignment, we have the following result.
Theorem 4 For k nonnegative integers
, a graph G with at least k vertices has a restricted size k-role assignment if and only if
can be partitioned into k nonempty sets
, and the following two properties are satisfied.
•
has no isolated vertices or all isolated vertices, where
, and
• for each
, there exist
sets
, where
, such that for any
,
when
, and
when
.
Proof. For k nonnegative integers
, let r be a restricted size k-role assignment of graph G and
. Then we have
for all
, in which
. The following is similar to the proof of Theorem 2.
When
, we have the following corollary for the restricted s-size k-role assignment.
Corollary 1 A graph G with at least k vertices has a restricted s-size k-role assignment if and only if
can be partitioned into k nonempty sets
, and the following two properties are satisfied.
•
has no isolated vertices or all isolated vertices, where
, and
• for each
, there exist
sets
, where
, such that for any
,
when
, and
when
.
4. k-Threshold Close Role Assignable Graphs
Roberts [3] showed that every graph G has a k-threshold role assignment for every
. Roberts [3] [11] showed that every graph with k or more vertices is k-threshold close role assignable for the cases
and 5.
Let
denote the set of all positive integers less or equal to
and the diameter of a graph G be defined as
(4)
Then we have the following result.
Theorem 5 Given a connected graph G. If
, then G is k-threshold close role assignable for any
.
Proof. Without loss of generality, we may assume that there are two vertices
such that
, i.e., x and y are the endpoints of some path of G. We partition
into
nonempty sets
by the following way: Let
(5)
Then it is easy to see that
and the following properties are valid.
•
,
•
, when
, and
• for any
and
, where
.
Note that
may be null or not.
Now we construct other
nonempty sets
from
. Let
(6)
in which
,
and
,
.
Then
,
when
, and for any vertex
,
the neighborhood
must be one of the following four cases.
•
,
•
,
•
,
•
.
Then, for any
, let
for
, and
for
. Then
for any vertex
. For any vertex
,
must be
or
. For any vertex
where
, since
is in one of the four cases above,
must be one of the following four sets:
,
,
and
. Thus it is easy to see that
for any two vertices u and v with same role, i.e., r is a k-threshold close role assignment of G. The proof is complete.
Corollary 2 Any graph that has no isolated vertices or all isolated vertices is k-threshold close role assignable for any
, where
,
is the number of components of G and
is the diameter of each component of G,
.
Proof. When all vertices of G are isolated vertices, the result is obvious. Now we assume that G has no isolated vertices and that
are the connected components of G. For each
, we define
as
for G in Theorem 5, where
. Furthermore, we order them as follows:
For any
, we assign all the vertices of the ith set in above sequence with role i, where
, and assign all vertices of the other sets with role k. Then the result is valid by the similar discussion in Theorem 5.
The following three results are immediate from Theorem 5.
Corollary 3 Any path with n vertices is k-threshold close role assignable for any
.
Corollary 4 Any tree whose longest path has t vertices is k-threshold close role assignable for any
.
Corollary 5 Any cycle with n vertices is k-threshold close role assignable for
any
.
Remark. Any cycle C with n vertices is k-threshold close role assignable for any
. In fact, let
or
be the n vertices of C in clockwise order. For any
, let
for any
,
and
for
. Then it is easy to see that r is a k-threshold close role assignment of C.
5. Maximal and Minimal k-Role Assignable Graphs
Suppose graph G with n vertices is k-role assignable. We may add (or delete) edges on G to get a complete (or empty) graph
. It is easy to see that
is k-role assignable too. So we can maximize or minimize the graph G and keep
fixedness for any
such that the resulting graph is still k-role assignable.
For a given k-role assignment r of graph G, the maximal (minimal, respectively) k-role assignable graph respect to r, denoted by
(
, respectively), is the graph that will get by the following ways.
If
, where
, we may use the following ways to get
.
• If
has no isolated vertices, then add some edges to join each pair of vertices unconnected in
, where
.
• If
, where
and
,
, then add some edges on graph G such that each vertex of
joins with every vertex of
.
We may also use the following ways to get
.
• If
has no isolated vertices, then delete some edges of
at mostly and keep
without any isolated vertex, where
.
• If
, where
and
,
, then delete some edges between
and
at mostly but keeping
for any
and
for any
.
By the ways of constructing
and
, the following theorem is obvious.
Theorem 6 If a graph G is k-role assignable, then both
and
are all k-role assignable. Furthermore,
(
, respectively) is the maximal (mini- mal, respectively) k-role assignable graph such that
keeps fixedness for any
, where r is some k-role assignment of graph G.
Acknowledgements
We thank the editor and the referee for their valuable comments. The work was supported in part by the Natural Science Foundation of Hebei Province of China under Grant A2015106045, and in part by the Institute of Applied Mathematics of Shijiazhuang University.