Designs associated with maximum independent sets of a graph | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

Designs associated with maximum independent sets of a graph

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

A (v, β o , μ)-design over regular graph G = (V, E) of degree d is an ordered pair D = (V, B), where |V| = v and B is the set of maximum independent sets of G called blocks such that if i, j ∈ V, i ≠ j and if i and j are not adjacent in G then there are exactly μ blocks containing i and j. In this paper, we study (v, β o , μ)-designs over the graphs K n × K n , T(n)-triangular graphs, L 2(n)-square lattice graphs, Petersen graph, Shrikhande graph, Clebsch graph and the Schläfli graph and non-existence of (v, β o , μ)-designs over the three Chang graphs T 1(8), T 2(8) and T 3(8).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berge C.: Theory of Graphs and its Applications. Wiley, New York (1962)

    MATH  Google Scholar 

  2. Cvetkovic D.M., Doob M., Sachs H.: Spectra of Graphs: Theory and Applications. Academic Press, New York (1980)

    Google Scholar 

  3. Chang L.C.: The uniqueness and non-uniqueness of the triangular association scheme. Sci. Record Peking Math. (New Ser.) 3, 604–614 (1959)

    MATH  Google Scholar 

  4. Farrel E.J.: An introduction to matching polynomials. J. Combin. Theory Ser. (B) 27, 75–86 (1979)

    Article  MathSciNet  Google Scholar 

  5. Godsil C., Royl G.: Algebraic Graph Theory. Springer-Verlag, New York (2001)

    MATH  Google Scholar 

  6. Harary F.: Graph Theory. Addison-Wesley, Reading, Mass (1969)

    Google Scholar 

  7. Harary F., Robinson R.W., Wormald N.C.: Isomorphic factorization-I: complete graphs. Trans. Am. Math. Soc. 242, 243–260 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  8. Holtan D.A., Sheehan J.: The Petersen Graph. Cambridge University Press, Cambridge (1993)

    Book  Google Scholar 

  9. Ionin Y.J., Shrikhande M.S.: On classification of two-class partially balanced designs. J. Stat. Plan. Inform. 95, 209–228 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. DI Paola J.W.: Block designs and graph theory. J. Combin. Theory 1, 132–148 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  11. Pedersen R.M.: The Shrikhande graph, Wolfram. http://mathworld.colfram.com/ShrikhandeGraph.html (2007).

  12. Raghavarao D.: Construction and Combinatorial Problems in Design of Experiments. John Wiley, New York (1971)

    Google Scholar 

  13. Seidel J.J.: Strongly regular graph with (−1,1,0) adjacency matrix having eigen value 3. Lin. Alg. Appl. 1, 281–298 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  14. Walikar H.B., Ramane H.S., Acharya B.D., Shekhareppa H.S., Arumugum S.: Partially balanced incomplete block design arising from minimum dominating sets of paths and cycles. AKCE J. Graphs Combin. 4(2), 223–232 (2007)

    MATH  Google Scholar 

  15. Walikar H.B., Shirkol S., Motammanavar S.V.: Designs associated with minimum dominating sets of Clebsch graph (to appear).

  16. Weisstein E.W.: Generalized Quadrangle, from MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/GeneralizedQuadrangle.html.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Karnatak University, Dharwad, 580003, India

    H. B. Walikar & Shailaja S. Shirkol

  2. SRC-IIIDMS, University of Mysore, Mysore, 570006, India

    B. D. Acharya

Authors
  1. H. B. Walikar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. D. Acharya
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shailaja S. Shirkol
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H. B. Walikar.

Additional information

Communicated by W. H. Haemers.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Walikar, H.B., Acharya, B.D. & Shirkol, S.S. Designs associated with maximum independent sets of a graph. Des. Codes Cryptogr. 57, 91–105 (2010). https://doi.org/10.1007/s10623-009-9351-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-009-9351-6

Keywords

Mathematics Subject Classification (2000)

Search

Navigation