NDLI: Representing Graphs in Steiner Triple Systems

Content Provider	Springer Nature Link
Author	Archdeacon, Dan Psomas, Costas Griggs, Terry
Copyright Year	2013
Abstract	Let G = (V, E) be a simple graph and let T = (P, B) be a Steiner triple system. Let φ be a one-to-one function from V to P. Any edge e = {u, v} has its image {φ(u), φ(v)} in a unique block in B. We also denote this induced function from edges to blocks by φ. We say that T represents G if there exists a one-to-one function φ : V → P such that the induced function φ : E → B is also one-to-one; that is, if we can represent vertices of the graph by points of the triple system such that no two edges are represented by the same block. In this paper we examine when a graph can be represented by an STS. First, we find a bound which ensures that every graph of order n is represented in some STS of order f(n). Second, we find a bound which ensures that every graph of order n is represented in every STS of order g(n). Both of these answers are related to finding an independent set in an STS. Our question is a generalization of finding such independent sets. We next examine which graphs can be represented in STS’s of small orders. Finally, we give bounds on the orders of STS’s that are guaranteed to embed all graphs of a given maximum degree.
Ending Page	266
Page Count	12
Starting Page	255
File Format	PDF
ISSN	09110119
e-ISSN	14355914
Journal	Graphs and Combinatorics
Issue Number	2
Volume Number	30
Language	English
Publisher	Springer Japan
Publisher Date	2013-01-16
Publisher Place	Tokyo
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Steiner triple system Graph representation Independent set Graph representations (geometric and intersection representations, etc.) Engineering Design Combinatorics Triple systems
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Minimum Difference Representations of Graphs

Silver Block Intersection Graphs of Steiner 2-Designs

Colouring Cubic Graphs by Small Steiner Triple Systems

The Fine Intersection Problem for Steiner Triple Systems

Automorphic Decompositions of Graphs

On the Intersection Problem for Steiner Triple Systems of Different Orders

Towards a Characterization of Leaf Powers by Clique Arrangements

The intrinsic dimensionality of graphs

Generalized Matrogenic Graphs

Representing Graphs in Steiner Triple Systems

Similar Documents

Minimum Difference Representations of Graphs

Silver Block Intersection Graphs of Steiner 2-Designs

Colouring Cubic Graphs by Small Steiner Triple Systems

The Fine Intersection Problem for Steiner Triple Systems

Automorphic Decompositions of Graphs

On the Intersection Problem for Steiner Triple Systems of Different Orders

Towards a Characterization of Leaf Powers by Clique Arrangements

The intrinsic dimensionality of graphs

Generalized Matrogenic Graphs

Representing Graphs in Steiner Triple Systems