Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T22:24:33.540Z Has data issue: false hasContentIssue false
  • English
  • Français

THE GENERAL POSITION NUMBER OF THE CARTESIAN PRODUCT OF TWO TREES

Part of: Graph theory

Published online by Cambridge University Press:  04 December 2020

JING TIAN Open the ORCID record for JING TIAN [Opens in a new window] ,
KEXIANG XU Open the ORCID record for KEXIANG XU [Opens in a new window]  and
SANDI KLAVŽAR Open the ORCID record for SANDI KLAVŽAR [Opens in a new window]
JING TIAN
Affiliation:
College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu210016, PR China e-mail: [email protected]
KEXIANG XU*
Affiliation:
College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu210016, PR China
SANDI KLAVŽAR
Affiliation:
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia; Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia e-mail: [email protected]
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The general position number of a connected graph is the cardinality of a largest set of vertices such that no three pairwise-distinct vertices from the set lie on a common shortest path. In this paper it is proved that the general position number is additive on the Cartesian product of two trees.

Keywords

Cartesian productgeneral position numbergeneral position settrees

MSC classification

Primary: 05C05: Trees
Secondary: 05C12: Distance in graphs 05C35: Extremal problems
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 104 , Issue 1 , August 2021 , pp. 1 - 10
Check for updates
Copyright
© 2020 Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Kexiang Xu is supported by NNSF of China (grant no. 11671202 and the China–Slovene bilateral grant 12-9). Sandi Klavžar acknowledges financial support from the Slovenian Research Agency (research core funding P1-0297, projects J1-9109, J1-1693, N1-0095 and the bilateral grant BI-CN-18-20-008).

References

Anand, B. S., Ullas Chandran, S. V., Changat, M., Klavžar, S. and Thomas, E. J., ‘Characterization of general position sets and its applications to cographs and bipartite graphs’, Appl. Math. Comput. 359 (2019), 84–89.Google Scholar
Balakrishnan, R., Raj, S. F. and Kavaskar, T., ‘ $b$ -coloring of Cartesian product of trees’, Taiwanese J. Math. 20 (2016), 1–11.CrossRefGoogle Scholar
Ghorbani, M., Klavžar, S., Maimani, H. R., Momeni, M., Rahimi-Mahid, F. and Rus, G., ‘The general position problem on Kneser graphs and on some graph operations’, Discuss. Math. Graph Theory, to appear. Published online (24 January 2020).CrossRefGoogle Scholar
Imrich, W., Klavžar, S. and Rall, D. F., Topics in Graph Theory: Graphs and their Cartesian Product (A. K. Peters, Wellesley, MA, 2008).CrossRefGoogle Scholar
Klavžar, S., Patkós, B., Rus, G. and Yero, I. G., ‘On general position sets in Cartesian grids’, Preprint, 2019, arXiv:1907.04535 [math.CO].Google Scholar
Klavžar, S. and Rus, G., ‘The general position number of integer lattices’, Appl. Math. Comput. 390 (2021), Article ID 125664.Google Scholar
Klavžar, S. and Yero, I. G., ‘The general position problem and strong resolving graphs’, Open Math. J. 17 (2019), 1126–1135.CrossRefGoogle Scholar
Körner, J., ‘On the extremal combinatorics of the Hamming space’, J. Combin. Theory Ser. A 71 (1995), 112–126.CrossRefGoogle Scholar
Manuel, P. and Klavžar, S., ‘A general position problem in graph theory’, Bull. Aust. Math. Soc. 98 (2018), 177–187.CrossRefGoogle Scholar
Manuel, P. and Klavžar, S., ‘The graph theory general position problem on some interconnection networks’, Fund. Inform. 163 (2018), 339–350.Google Scholar
Patkós, B., ‘On the general position problem on Kneser graphs’, Ars Math. Contemp., to appear.Google Scholar
Shiu, W. C. and Low, R. M., ‘The integer-magic spectra and null sets of the Cartesian product of trees’, Australas. J. Combin. 70 (2018), 157–167.Google Scholar
Tian, J. and Xu, K., ‘The general position number of Cartesian products of trees or cycles with general graphs’, Preprint, 2020.CrossRefGoogle Scholar
Ullas Chandran, S. V. and Jaya Parthasarathy, G., ‘The geodesic irredundant sets in graphs’, Int. J. Math. Combin. 4 (2016), 135–143.Google Scholar
Wood, D. R., ‘Colouring the square of the Cartesian product of trees’, Discrete Math. Theor. Comput. Sci. 13 (2011), 109–111.Google Scholar