BibTex RIS Cite

Graphical sequences of some family of induced subgraphs

Year 2015, , 95 - 109, 30.04.2015
https://doi.org/10.13069/jacodesmath.39202

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.

References

  • 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.
  • P. Erdős, T. Gallai, Graphs with prescribed degrees, (in Hungarian) Matemoutiki Lapor, 11, 264-274, 1960.
  • D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math., 17, 166-177, 1965.
  • 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.
  • J. L. Gross, J. Yellen, P. Zhang, Handbook of graph theory, CRC Press, Boca Raton, FL, 2013.
  • 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.
  • 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.
  • S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math 38(1), 73-81, 2014.
  • A. R. Rao, An Erdos-Gallai type result on the clique number of a realization of a degree sequence, Preprint.
  • 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.
Year 2015, , 95 - 109, 30.04.2015
https://doi.org/10.13069/jacodesmath.39202

Abstract

References

  • 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.
  • P. Erdős, T. Gallai, Graphs with prescribed degrees, (in Hungarian) Matemoutiki Lapor, 11, 264-274, 1960.
  • D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math., 17, 166-177, 1965.
  • 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.
  • J. L. Gross, J. Yellen, P. Zhang, Handbook of graph theory, CRC Press, Boca Raton, FL, 2013.
  • 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.
  • 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.
  • S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math 38(1), 73-81, 2014.
  • A. R. Rao, An Erdos-Gallai type result on the clique number of a realization of a degree sequence, Preprint.
  • 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.
There are 10 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

S. Pirzada This is me

Bilal A. Chat This is me

Farooq A. Dar This is me

Publication Date April 30, 2015
Published in Issue Year 2015

Cite

APA Pirzada, S., Chat, B. A., & Dar, F. A. (2015). Graphical sequences of some family of induced subgraphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(2), 95-109. https://doi.org/10.13069/jacodesmath.39202
AMA Pirzada S, Chat BA, Dar FA. Graphical sequences of some family of induced subgraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. April 2015;2(2):95-109. doi:10.13069/jacodesmath.39202
Chicago Pirzada, S., Bilal A. Chat, and Farooq A. Dar. “Graphical Sequences of Some Family of Induced Subgraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, no. 2 (April 2015): 95-109. https://doi.org/10.13069/jacodesmath.39202.
EndNote Pirzada S, Chat BA, Dar FA (April 1, 2015) Graphical sequences of some family of induced subgraphs. Journal of Algebra Combinatorics Discrete Structures and Applications 2 2 95–109.
IEEE S. Pirzada, B. A. Chat, and F. A. Dar, “Graphical sequences of some family of induced subgraphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 2, pp. 95–109, 2015, doi: 10.13069/jacodesmath.39202.
ISNAD Pirzada, S. et al. “Graphical Sequences of Some Family of Induced Subgraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/2 (April 2015), 95-109. https://doi.org/10.13069/jacodesmath.39202.
JAMA Pirzada S, Chat BA, Dar FA. Graphical sequences of some family of induced subgraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:95–109.
MLA Pirzada, S. et al. “Graphical Sequences of Some Family of Induced Subgraphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 2, 2015, pp. 95-109, doi:10.13069/jacodesmath.39202.
Vancouver Pirzada S, Chat BA, Dar FA. Graphical sequences of some family of induced subgraphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(2):95-109.

Cited By

On multigraphic and potentially multigraphic sequences
Acta Universitatis Sapientiae, Informatica
Shariefuddin Pirzada
https://doi.org/10.1515/ausi-2017-0003