×

The common-neighbourhood of a graph. (English) Zbl 1424.05167

Summary: The most widely used and well-known vulnerability measures of a connected graph are based on the neighbourhood concept. It takes into account neighbour-integrity, edge-integrity and accessibility number. In this work we define and examine common-neighbourhood of a connected graph as a new global connectivity measure. Our measure examines the neighbourhoods of all pairs of vertices of any connected graph. We show that, for connected graphs \(G_1\) and \(G_2\) of the same order, if the dominating number of \(G_1\) is bigger than the dominating number of \(G_2\), then the common-neighbourhood of \(G_1\) is less than the common-neighbourhood of \(G_2\). We give some theorems and obtain some results on common-neighbourhood of a graph. We consider all the graphs in this paper as connected, undirected and without loops.

MSC:

05C40 Connectivity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Bagga K.S., Beineke L.W., Goddard W.D., Lipman M.J, and Pippert R.E., A Survey of Integrity, Discrete Applied Math. 37/38, 13-28, (1992). · Zbl 0778.05041
[2] Bagga K.S., Beineke L.W., Pippert R.E., and Sedlmeyer R.L, Some Bounds and An Algorithm For The Edge-integrity of Trees, Ars Combinatoria.35-A,225- 238, (1993). · Zbl 0840.05037
[3] Bagga K.S., Beineke L.W., and Pippert R.E, On the Honesty of Graph Complements, Discrete Math. 122, 1-6, (1993). · Zbl 0796.05060
[4] Bagga K.S, Beineke L.W., and Pippert R.E., Edge Integrity: A Survey, Discrete Math., 124, 3-12, (1994). · Zbl 0796.05061
[5] Barefoot C.A, Entringer R., and Swart H., Vulnerability in Graphs-A Comparative Survey. J.Comb.Math.Comb.Comput. 1, 13-22, (1987). · Zbl 0646.05042
[6] Barefoot placecountry-regionC.A., Entringer R., and Swart H., Integrity of Trees and Powers of Cycles, Congressus Numeratum 58, 103-114, (1987).
[7] Beineke L.W., Oellermann O.R., Pippert R.E., The Common Connectivity of A Graph, Discrete Mathematics,252,pp.31-45, (2002). · Zbl 1002.05040
[8] Chvatal V., Tough Graphs and Hamiltonian Circuits, Discrete Math.5, 215- 218, (1973). · Zbl 0256.05122
[9] Cozzens M., Stability Measures and Data Fusion Networks, Graph Theory Notes of New York XXVI, pp.8-14, (1994).
[10] Cozzens M., Moazzami D., Stueckle S., The Tenacity of A Graph, Graph Theory, Combinatorisc, Algorithms and Applications. Vol 2., (1995). · Zbl 0845.05088
[11] Cozzens. M., Moazzami D., and Stueckle S., The Tenacity of Harary Graphs, J.Comb. Math. Comb. Comput. 16, 33-56, (1994). · Zbl 0814.05053
[12] Cozzens M.B., Stability Measures and Data Fusion Networks, Graph Theory Notes of Newyork XXVI, 8-14, (1994).
[13] Cozzens M.B., and Wu S.Y, Bounds of Edge Neighbour-integrity of Graphs, Australian J.of Combinatorics 15, 71-80, (1997). · Zbl 0878.05048
[14] Cozzens, M.B. and Wu S.Y., Vertex Neighbour-integrity of Trees, Ars. Combinatoria 43, 169-180, (1996). · Zbl 0881.05064
[15] Dündar P., Aytac A., Integrity of Total Graphs via Some Parameters, Mathematical Notes Vol.76, N5, 665-672, (2004). · Zbl 1063.05114
[16] Dündar P., Accessibility Number and the Neighbour-integrity of Generalised Petersen Graphs, Neural Network World, Vol.2, 167-174, (2001).
[17] Dündar P., Aytaç A. and Aytaç V., Calculation of Accessibility Number and Neighbourintegrity of a Graph, Mathematical Notes,Vol.78, N5,631-640, (2005). · Zbl 1124.05317
[18] Dündar P., Stability Measures of Some Static Interconnection Networks, Int.J. Computer Math. Vol.76, 455-462, (2001). · Zbl 0984.68117
[19] Dündar P., and Ozan A., The Neighbour-integrity of Sequential Joined Graphs, Intern. J. Computer Math.vol.74, 45-52, (2000). · Zbl 0961.05044
[20] Lesniak L., Chartrand G., Graphs and Digraphs, placeStateCalifornia Wadsworth & Brooks, (1986)
[21] West D.B., Introduction to Graph Theory, Prentice Hall, NJ, (2001).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.