E. Sampathkumar and M. A. Sriraj

Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132

Volume 19, 2013, Number 4, Pages 16—27

**Download 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

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

- 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.
- 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.
- 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.
- Harary, F. Graph Theory, Addison-Wesley, Reading, MA, 1969.
- Sampathkumar, E. Point-signed and line-signed graphs, Nat. Acad. Sci. Letters, Vol. 7, 1984, No. 3, 91–93.
- 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. - Sampathkumar, E.,M. S. Subramanya, P. Siva Kota Reddy, Directonally
*n*-signed graphs-II, Intenational. J. Math and Combin, Vol. 4, 2009, 89–98. - 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. - 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. - Zaslavsky, T. Orientation of signed graphs, Europ. J. Combin., Vol. 12, 1991, No. 4, 361–375.
- 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.
- 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.

## Related papers

## Cite this paper

APASampathkumar, E., & Sriraj, M. A.(2013). (2, *d*)-Sigraphs, Notes on Number Theory and Discrete Mathematics, 19(4), 16-27.

Sampathkumar, E, and M. A. Sriraj. “(2, *d*)-Sigraphs.” Notes on Number Theory and Discrete Mathematics 19, no. 4 (2013): 16-27.

Sampathkumar, E, and M. A. Sriraj. “(2, *d*)-Sigraphs.” Notes on Number Theory and Discrete Mathematics 19.4 (2013): 16-27. Print.