×

zbMATH — the first resource for mathematics

The representation number of some sparse graphs. (English) Zbl 1251.05090
Summary: We study the representation number for some special sparse graphs. For graphs with a single edge and for complete binary trees we give an exact formula, and for hypercubes we improve the known lower bound. We also study the prime factorization of the representation number of graphs with one edge.

MSC:
05C42 Density (toughness, etc.)
05C65 Hypergraphs
05C62 Graph representations (geometric and intersection representations, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akhtar, R.; Evans, A.B.; Pritikin, D., Representation numbers of stars, Integers, 10, 733-745, (2010) · Zbl 1214.05146
[2] Akhtar, R.; Evans, A.B.; Pritikin, D., Representation numbers of complete multipartite graphs, Discrete math., 3112, 1158-1165, (2012) · Zbl 1238.05178
[3] Erdös, P.; Evans, A.B., Representations of graphs and orthogonal Latin square graphs, J. graph theory, 13, 5, 593-595, (1989) · Zbl 0691.05053
[4] Evans, A.B., Representations of disjoint unions of complete graphs, Discrete math., 307, 9-10, 1191-1198, (2007) · Zbl 1112.05070
[5] Evans, A.B.; Fricke, G.; Maneri, C.; McKee, T.; Perkel, M., Representations of graphs modulo \(n\), J. graph theory, 18, 8, 801-815, (1994) · Zbl 0815.05059
[6] Evans, A.B.; Isaak, G.; Narayan, D., Representations of graphs modulo \(n\), Discrete math., 223, 1-3, 109-123, (2000) · Zbl 0969.05046
[7] Lindner, C.; Mendelsohn, E.; Mendelsohn, N.S.; Wolk, B., Orthogonal Latin square graphs, J. graph theory, 3, 4, 325-338, (1979) · Zbl 0422.05058
[8] Lovász, L.; Nešetřil, J.; Pultr, A., On a product dimension of graphs, J. combin. theory ser. B, 29, 1, 47-67, (1980) · Zbl 0439.05038
[9] Narayan, D., An upper bound for the representation number of graphs with fixed order, Integers, 3, 4, (2003), A12 (electronic) · Zbl 1023.05104
[10] Narayan, D.; Urick, J., Representations of split graphs, their complements, stars, and hypercubes, Integers, 7, 13, (2007), A9 (electronic) · Zbl 1114.05090
[11] Rosser, J.B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. math., 6, 64-94, (1962) · Zbl 0122.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.