On a tree-partition problem期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

On a tree-partition problem

Institution:	1. University of Tennessee, Knoxville, TN, United States;2. Oak Ridge National Laboratory, Oak Ridge, TN, United States;1. National Laboratory Astana, Center for Energy and Advanced Materials Science, Laboratory of energy ecology and climate, Astana, Kazakhstan;2. E4SMA, Via Livorno 60, Torino, Italy;3. Nazarbayev University, Astana, Kazakhstan;1. Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina;2. CONICET-Universidad de Buenos Aires, Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, Argentina;1. Electrical Engineering Department, Tehran South Branch, Tehran, Iran;2. Shahid Sattari University, Tehran, Iran;1. Department of Biotechnology, Kumaun University, Bhimtal Campus, Bhimtal, Uttarakhand, India;2. Department of Mechanical Engineering, G. B. Pant Institute of Engineering and Technology, Pauri Garhwal, Uttarakhand, India;3. Department of Botany, Kumaun University, S.S.J Campus, Almora, Uttarakhand, India;1. Performance Analysis Center of Production and Operations Systems (PacPos), Northwestern Polytechnical University, Xi?an, Shaanxi 710072, PR China;2. Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Ministry of Education, Northwestern Polytechnical University, Xi?an, Shaanxi 710072, PR China;3. Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, United States

Abstract:	If $T = (V, E)$ is a tree then – T denotes the additive hereditary property consisting of all graphs that does not contain T as a subgraph. For an arbitrary vertex v of T we deal with a partition of T into two trees $T_{1}$ , $T_{2}$ , so that $V (T_{1}) \cap V (T_{2}) = {v}$ , $V (T_{1}) \cup (T_{2}) = V (T)$ , $E (T_{1}) \cap E (T_{2}) = ?$ , $E (T_{1}) \cup E (T_{2}) = E (T)$ , $T V (T_{1}) \ {v}] ? E (T_{1})$ and $T V (T_{2}) \ {v}] ? E (T_{2})$ . We call such a partition a $T_{v} ? p a r t i t i o n$ of T. We study the following em: Given a graph G belonging to –T. Is it true that for any $T_{v}$ -partition $T_{1}$ , $T_{2}$ of T there exists a partition ${V_{1}, V_{2}}$ of the vertices of G such that $G V_{1}] \in ? T_{1}$ and $G V_{2}] \in ? T_{2}$ ? This problem provides a natural generalization of Δ-partition problem studied by L. Lovász (L. Lovász, On decomposition of graphs. Studia Sci. Math. Hungar. 1 (1966) 237–238]) and Path Partition Conjecture formulated by P. Mihók (P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86]). We present some partial results and a contribution to the Path Kernel Conjecture that was formulated with connection to Path Partition Conjecture.

Keywords:
本文献已被 ScienceDirect 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏