Printer Friendly

TVS OF CONVEX POLYTOPE GRAPHS WITH PENDENT EDGES.

Byline: Ali Ahmad

Abstract:

A total vertex irregular k-labeling Ph of a graph G is a labeling of the vertices and edges of G with labels from the set{1,2,L,k} in such a way that for any two different vertices and their weights and are distinct. Here, the weight of a vertex in is the sum of the label of and the labels of all edges incident with the vertex . The minimum for which the graph has a vertex irregular total -labeling is called the total vertex irregularity strength of G.

I have determined an exact value of the total vertex irregularity strength of some convex polytope graphs with pendant edges.

Key Words: vertex irregular total -labeling, total vertex irregularity strength, irregular assignments, convex polytope graphs, pendent edges.

1. INTRODUCTION

Let us consider a simple (without loops and multiple edges) undirected graph . For a graph we define a labeling to be a total vertex irregular -labeling of the graph if for every two different vertices and of one has where the weight of a vertex in the labeling is

where is the set of neighbors of . In [3] Baca, Jendrol , Miller and Ryan defined a new graph invariant, called the total vertex irregularity strength of that is the minimum for which the graph has a vertex irregular total k-labeling.

The original motivation for the definition of the total vertex irregularity strength came from irregular assignments and the irregularity strength of graphs introduced in [6] by Chartrand, Jacobson, Lehel, Oellermann, Ruiz and Saba, and studied by numerous authors [5, 7, 8, 9, 11].

The irregularity strength can be interpreted as the smallest integer for which can be turned into a multigraph by replacing each edge by a set of at most parallel edges, such that the degrees of the vertices in are all different.

It is easy to see that irregularity strength of a graph is defined only for graphs containing at most one isolated vertex and no connected component of order 2. On the other hand, the total vertex irregularity strength is defined for every graph.

If an edge labeling provides the irregularity strength , then we extend this labeling to total labeling in such a way

Thus, the total labeling is a vertex irregular total labeling and for graphs with no component of order is.

Nierhoff [12] proved that for all -graphs with no component of order at most 2 and , the irregularity strength . From this result it follows that

In [3] several bounds and exact values of were determined for different types of graphs (in particular for stars, cliques and prisms). Among others, the authors proved the following theorem

Theorem 1 [3]: Let be a graph with minimum degree and maximum degree.

Wijaya and Slamin [14] found the exact values of the total vertex irregularity strength of wheels, fans, suns and friendship graphs. Wijaya, Slamin, Surahmat and Jendrol [15] determined an exact value for complete bipartite graphs. Ahmad and Baca [1] found an exact value of the total vertex irregularity strength for Jahangir graphs and circulant graphs.

The main aim of this paper is determined an exact value of the total vertex irregularity strength of some convex polytope graphs.

Main Results:

The graph of convex polytope (Figure 1) is obtained by the combination of the graph of convex polytope [4] and the graph of a prism, and attaching a pendant edge at each Vertex of outer Let

Proof:

The convex polytope has vertices of degree 1, vertices of degree 4 and vertices of degree 5.

To prove the lower bound we consider the weights of the vertices. The smallest weight among all vertices of is at least 2, so the largest weight of a vertex of degree 1 is at least . Since the weight of any vertex of degree 1 is the sum of two positive integers, so at least one label is at least

Thus, the weights of vertices successively attain distinct values.

The labeling is the desired vertex irregular total -labeling and provides the upper bound on . Combining with the lower bound, we conclude that

REFERENCES

[1] A. Ahmad and M. Baca, On vertex irregular total labelings, Ars Combin., to appear.

[2] M. Anholcer, M. Kalkowski and J. Przybylo, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math. 309 (2009), 6316-6317.

[3] M. Baca, S. Jendrol, M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007), 1378-1388.

[4] M. Baca, On magic labellings of convex polytopes, Annals Disc. Math. 51 (1992), 13-16.

[5] T. Bohman and D. Kravitz, On the irregularity strength of trees, J.Graph Theory 45 (2004), 241-254.

[6] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988), 187-192.

[7] R.J. Faudree, M.S. Jacobson, J. Lehel and R.H. Schlep, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. 76 (1988), 223-240.

[8] A. Frieze, R.J. Gould, M. Karonski, and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002), 120-137.

[9] A. Gy'arf'as, The irregularity strength of is 4 for odd m, Discrete Math. 71 (1988), 273-274.

[10] M. Imran, S.A. Bokhary, A.Q. Baig, On families of convex polytopes with constant metric dimension, computer and Mathematics with Applications 60 (2010) 2625-2638.

[11] S. JendroV l, M. Tk'aVc and Z. Tuza, The irregularity strength and cost of the union of cliques, Discrete Math. 150 (1996), 179-186.

[12] T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000), 313-323.

[13] J. Przybylo, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math. 23 (2009), 511-516.

[14] K. Wijaya and Slamin, Total vertex irregular labeling of wheels, fans, suns and friendship graphs, JCMCC 65 (2008), 103-112.

[15] K. Wijaya, Slamin, Surahmat, S. Jendrol, Total vertex irregular labeling of complete bipartite graphs, JCMCC 55 (2005), 129-136.

Ali Ahmad

Department of Mathematics, Govt. College University, Lahore, Pakistan ahmadsms@gmail.com,
COPYRIGHT 2011 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Ahmad, Ali
Publication:Science International
Article Type:Report
Geographic Code:9PAKI
Date:Jun 30, 2011
Words:1011
Previous Article:COMPUTATIONAL APPROACHES FOR GENE PREDICTION: A COMPARATIVE SURVEY.
Next Article:MANETs ON-DEMAND ROUTING PROTOCOLS IN CONTEXT OF ENERGY CONSUMPTION.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters