2013/09/01 by Jun-Lin Guo, Tao-Ming Wang, Guo, Jun-Lin +5
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1309.0170
openalex publication_date 2013/09/01 · arxiv created 2013/09/03 · arxiv updated 2013/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph with vertex set V(G) and edge set E(G). A family S of nonempty sets \S1,…,Sn\ is a set representation of G if there exists a one-to-one correspondence between the vertices v1, …, vn in V(G) and the sets in S such that vivj ∈ E(G) if and only if Si∩ Sj≠ \es. A set representation S is a distinct (respectively, antichain, uniform and simple) set representation if any two sets Si and Sj in S have the property Si≠ Sj (respectively, Si\nsubseteq Sj, |Si|=|Sj| and |Si∩ Sj|\leqslant 1). Let U(S)=\bigcupi=1n Si. Two set representations S and S' are isomorphic if S' can be obtained from S by a bijection from U(S) to U(S'). Let F denote a class of set representations of a graph G. The type of F is the number of equivalence classes under the isomorphism relation. In this paper, we investigate types of set representations for linegraphs. We determine the types for the following categories of set representations: simple-distinct, simple-antichain, simple-uniform and simple-distinct-uniform.