(2, d)-Sigraphs

E. Sampathkumar and M. A. Sriraj
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 19, 2013, Number 4, Pages 16–27
Full paper (PDF, 238 Kb)

Details

Authors and affiliations

E. Sampathkumar
Department of Studies in Mathematics, University of Mysore
Mysore–570 006, India

M. A. Sriraj
Department of Mathematics, Vidyavardhaka College of Engineering
P.B. No.206, Gokulam III Stage
Mysore–570 002, India

Abstract

An edge uv in a graph G is directionally labeled by an ordered pair ab if the label ℓ(uv) on uv is ab in the direction from u to v; and ℓ(vu) = ba. A (2, d)-sigraph G = (V, E) is a graph in which every edge is directionally labeled by an ordered pair ab ∈ {++, −−, +−, −+}. A (2, d)-sigraph G has a uniform-directional edge labeling (ude-labeling) at a vertex u in G, if for each neighbor v of u, either ℓ(vu) ∈ {++, +−} or ℓ(vu) ∈ {−−, −+}. Further, G is ude-balanced if it has such a labeling at each of its vertex. Two characterizations of ude-balanced (2, d)-sigraphs are obtained. Using a notion of 2-splitting of a (2, d)-sigraphs, we define a 2-balanced (2, d)-sigraph, and obtain a characterization of 2-balanced (2, d)-sigraph which is similar to a characterization of balanced sigraphs. Further, the notion of clusterability of signed graphs is extended to (2, d)-sigraphs, and a characterization of clusterable (2, d)-sigraph is obtained. The notions of ude-balance and clusterability are extended to (n, d)-sigraphs. Some applications of (2, d)-sigraphs are also mentioned.

Keywords

• Signed graph
• Directional adjacency
• (2, d)-sigraph
• Uniform directional labeling
• Clusterability
• Bidirected graph

AMS Classification

• 05C22
• 05B20

References

1. Davis, J. A. Clustering and structural balance in graphs, Human Relations, Vol. 20, 1967, 181–187. Reprinted in: Social Networks: A Developing Paradigm (Ed.: Samuel Leinhardt) Academic Press, New York, 1977, pp. 27–33.
2. Edmonds, J., E. L. Johnson, Matching: a well-solved class of integral linear programs. Combinatorial Structures and Their Applications (Richard Guy, et al., eds.). Proc. Calgary Int. Conf., Calgary, 1969, 89–92. Gordon and Breach, New York, 1970.
3. Harary, F. On the notion of balance of a signed graph, Michigan Math. J., Vol. 2, 1953–54, 143–146 and addendum preceding p.1.
4. Harary, F. Graph Theory, Addison-Wesley, Reading, MA, 1969.
5. Sampathkumar, E. Point-signed and line-signed graphs, Nat. Acad. Sci. Letters, Vol. 7, 1984, No. 3, 91–93.
6. Sampathkumar, E., P. Siva Kota Reddy, M. S. Subramanya, Directionally n-signed Graphs, Proc. ICDM 2008, RMS-Lecture Notes Series, Vol. 13, 2010, 153–160.
7. Sampathkumar, E.,M. S. Subramanya, P. Siva Kota Reddy, Directonally n-signed graphs-II, Intenational. J. Math and Combin, Vol. 4, 2009, 89–98.
8. Sampathkumar, E., P. Siva Kota Reddy, M. S. Subramanya. (3, d)-sigraph and its applications, Advn. Stud. Contemp. Math., Vol. 17, 2008, No. 1, 57–67.
9. Sampathkumar, E., P. Siva Kota Reddy, M. S. Subramanya. (3, d)-sigraph and its applications, Advn. Stud. Contemp. Math., Vol. 20, 2010, No. 1, 115–124.
10. Zaslavsky, T. Orientation of signed graphs, Europ. J. Combin., Vol. 12, 1991, No. 4, 361–375.
11. Sampathkumar, E., M. A. Sriraj, T. Zaslavsky, Directionally 2-Signed and Bidirected Graphs, J. of Combinatorics, Information and System Sciences, Vol. 37, 2012, No. 2–4, 373–377.
12. Zaslavsky, T. A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas, VII Edition, Electronic J. Combinatorics, Vol. 8, 1998, No. 1, Dynamic Surveys #8, 124 pp.