A general position problem in graph theory. (English) Zbl 1396.05033
Summary: The paper introduces a graph theory variation of the general position problem: given a graph \(G\), determine a largest set \(S\) of vertices of \(G\) such that no three vertices of \(S\) lie on a common geodesic. Such a set is a max-gp-set of \(G\) and its size is the gp-number \(\mathrm{gp}(G)\) of \(G\). Upper bounds on \(\mathrm{gp}(G)\) in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.
MSC:
| 05C12 | Distance in graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
Keywords:
general position problem; isometric subgraph; packing; independence number; computational complexityReferences:
| [1] | Barnaby, M.; Raimondi, F.; Chen, T.; Martin, J., The packing chromatic number of the infinite square lattice is between 13 and 15, Discrete Appl. Math., 225, 136-142, (2017) · Zbl 1361.05051 · doi:10.1016/j.dam.2017.03.013 |
| [2] | Beaudou, L.; Gravier, S.; Meslem, K., Subdivided graphs as isometric subgraphs of Hamming graphs, European J. Combin., 30, 1062-1070, (2009) · Zbl 1205.05189 · doi:10.1016/j.ejc.2008.09.011 |
| [3] | Brešar, B.; Klavžar, S.; Rall, D. F.; Wash, K., Packing chromatic number, (1, 1, 2, 2)-colorings, and characterizing the Petersen graph, Aequationes Math., 91, 169-184, (2017) · Zbl 1355.05194 · doi:10.1007/s00010-016-0461-8 |
| [4] | Dankelmann, P., Average distance and generalised packing in graphs, Discrete Math., 310, 2334-2344, (2010) · Zbl 1210.05108 · doi:10.1016/j.disc.2010.05.006 |
| [5] | Dudeney, H. E., Amusements in Mathematics, (1917), Nelson: Nelson, Edinburgh |
| [6] | Fitzpatrick, S. L., The isometric path number of the Cartesian product of paths, Congr. Numer., 137, 109-119, (1999) · Zbl 0968.05043 |
| [7] | Froese, V.; Kanj, I.; Nichterlein, A.; Niedermeier, R., Finding points in general position, Internat. J. Comput. Geom. Appl., 27, 277-296, (2017) · Zbl 1386.68196 · doi:10.1142/S021819591750008X |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979), W. H. Freeman: W. H. Freeman, New York · Zbl 0411.68039 |
| [9] | Goddard, W.; Xu, H., The S-packing chromatic number of a graph, Discuss. Math. Graph Theory, 32, 795-806, (2012) · Zbl 1293.05106 · doi:10.7151/dmgt.1642 |
| [10] | Hartnell, B.; Whitehead, C. A., On k-packings of graphs, Ars Combin., 47, 97-108, (1997) · Zbl 0933.05122 |
| [11] | Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 225-233, (1975) · Zbl 0315.05102 · doi:10.2140/pjm.1975.61.225 |
| [12] | Misiak, A.; Stpień, Z.; Szymaszkiewicz, A.; Szymaszkiewicz, L.; Zwierzchowski, M., A note on the no-three-in-line problem on a torus, Discrete Math., 339, 217-221, (2016) · Zbl 1322.05034 · doi:10.1016/j.disc.2015.08.006 |
| [13] | Pan, J.-J.; Chang, G. J., Isometric-path numbers of block graphs, Inform. Process. Lett., 93, 99-102, (2005) · Zbl 1173.68612 · doi:10.1016/j.ipl.2004.09.021 |
| [14] | Pan, J.-J.; Chang, G. J., Isometric path numbers of graphs, Discrete Math., 306, 2091-2096, (2006) · Zbl 1100.05052 · doi:10.1016/j.disc.2006.04.003 |
| [15] | Payne, M.; Wood, D. R., On the general position subset selection problem, SIAM J. Discrete Math., 27, 1727-1733, (2013) · Zbl 1348.52012 · doi:10.1137/120897493 |
| [16] | Pěgřímek, D.; Gregor, P., Hamiltonian laceability of hypercubes without isometric subgraphs, Graphs Combin., 32, 2591-2624, (2016) · Zbl 1353.05037 · doi:10.1007/s00373-016-1728-5 |
| [17] | Polat, N., On isometric subgraphs of infinite bridged graphs and geodesic convexity, Discrete Math., 244, 399-416, (2002) · Zbl 0995.05045 · doi:10.1016/S0012-365X(01)00097-8 |
| [18] | Por, A.; Wood, D. R., No-three-in-line-in-3D, Algorithmica, 47, 481-488, (2007) · Zbl 1118.68106 · doi:10.1007/s00453-006-0158-9 |
| [19] | Shpectorov, S. V., Distance-regular isometric subgraphs of the halved cubes, European J. Combin., 19, 119-136, (1998) · Zbl 0887.05056 · doi:10.1006/eujc.1997.0136 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
