Graphical sequences of some family of induced subgraphs

Abstract

The subdivision graph $S(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. The $S_{vertex}$ or $S_{ver}$ join of the graph $G_{1}$ with the graph $G_{2}$, denoted by $G_{1}\dot{\vee}G_{2}$, is obtained from $S(G_{1})$ and $G_{2}$ by joining all vertices of $G_{1}$ with all vertices of $G_{2}$. The $S_{edge}$ or $S_{ed}$ join of $G_{1}$ and $G_{2}$, denoted by $G_{1}\bar{\vee}G_{2}$, is obtained from $S(G_{1})$ and $G_{2}$ by joining all vertices of $S(G_{1})$ corresponding to the edges of $G_{1}$ with all vertices of $G_{2}$. In this paper, we obtain graphical sequences of the family of induced subgraphs of $S_{J} = G_{1}\vee G_{2}$, $S_{ver} = G_{1}\dot{\vee}G_{2}$  and $S_{ed} = G_{1}\bar{\vee}G_{2}$. Also we prove that the graphic sequence of $S_{ed}$ is potentially $K_{4}-e$-graphical.

Keywords

• Graphical sequences, Subdivision graph, Join of graphs, Split graph

References

1. C. Bu, B. Yan, X. Zhou, J. Zhou, Resistance distance in subdivision-vertex join and subdivision-edge join of graphs, Linear Algebria and its Applications, 458, 454-462, 2014.
2. P. Erdős, T. Gallai, Graphs with prescribed degrees, (in Hungarian) Matemoutiki Lapor, 11, 264-274, 1960.
3. D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math., 17, 166-177, 1965.
4. R. J. Gould, M. S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in Combinatorics, Graph Theory and Algorithms, vol. 2, (Y. Alavi et al., eds.), New Issues Press, Kalamazoo MI, 451-460, 1999.
5. J. L. Gross, J. Yellen, P. Zhang, Handbook of graph theory, CRC Press, Boca Raton, FL, 2013.
6. S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, J. SIAM Appl. Math., 10, 496-506, 1962.
7. V. Havel, A Remark on the existance of finite graphs, (Czech) Casopis Pest. Mat. 80, 477-480, 1955. [8] S. Pirzada, An introduction to graph theory, Universities Press, Orient Blackswan, India, 2012.
8. S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math 38(1), 73-81, 2014.

9. A. R. Rao, An Erdos-Gallai type result on the clique number of a realization of a degree sequence, Preprint.
10. A. R. Rao, The clique number of a graph with a given degree sequence, Proc. Symposium on Graph Theory (ed. A. R. Rao), Macmillan and Co. India Ltd, I.S.I. Lecture Notes Series, 4, 251-267, 1979. [12] J. H. Yin, Conditions for r-graphic sequences to be potentially K(r)-graphic, Disc. Math., 309, m+1-graphic, Disc. Math., 309, 6271-6276, 2009.