* [78] Armin Haller et al.  “The modular SSN ontology: A joint W3C and OGC standard specifying the semantics of sensors, observations, sampling, and actuation”  In _Semantic Web_ 10.1 IOS Press, 2019, pp. 9–32
  * [79] Armin Haller et al.  “Semantic Sensor Network Ontology; Open Geospatial Consortium (OGC) & World Wide Web Consortium (W3C)” Accessed on April 16, 2024, 2020  URL: https://w3c.github.io/sdw/ssn
  * [80] Project Haystack  “An Open Source initiative to streamline working with IoT Data” Accessed on April 16, 2024, 2014  URL: https://project-haystack.org/
  * [81] Pascal Hitzler et al.  “OWL 2 web ontology language primer”  In _W3C recommendation_ 27.1, 2009, pp. 123
  * [82] Robert Hoehndorf  “What is an upper level ontology?”  In _Ontogenesis_ , 2010
  * [83] Jong-yi Hong, Eui-ho Suh and Sung-Jin Kim  “Context-aware systems: A literature review and classification”  In _Expert Systems with applications_ 36.4 Elsevier, 2009, pp. 8509–8522
  * [84] Tianzhen Hong, Yixing Chen and Sarah Taylor-Lange  “Occupant Behavior XML Schema”, 2015
  * [85] Tianzhen Hong, Simona D’Oca, William JN Turner and Sarah C Taylor-Lange  “An ontology to represent energy-related occupant behavior in buildings. Part I: Introduction to the DNAs framework”  In _Building and Environment_ 92 Elsevier, 2015, pp. 764–777
  * [86] Richard Hull and Roger King  “Semantic database modeling: Survey, applications, and research issues”  In _ACM Computing Surveys (CSUR)_ 19.3 ACM New York, NY, USA, 1987, pp. 201–260
  * [87] Building Smart International  “Industry Foundation Classes (IFC)” Accessed on April 16, 2024, 1997  URL: https://technical.buildingsmart.org/standards/ifc/
  * [88] Krzysztof Janowicz et al.  “SOSA: A lightweight ontology for sensors, observations, samples, and actuators”  In _Journal of Web Semantics_ 56 Elsevier, 2019, pp. 1–10
  * [89] Youngmin Ji, Woosuk Choi, Kisu Ok and Jooyoung Ahn  “Intelligent building using hybrid Inference with building automation system to improve energy efficiency”  In _Proc. of the 16th International Semantic Web Conference (ISWC)_ , 2017
  * [90] Andy Koronios, Daniela Nastasie, Vivek Chanana and Abrar Haider  “Integration through standards–an overview of international standards for engineering asset management”  In _Proc. of the 4th Int. Conference on Condition Monitoring (WCEAM-CM)_ , 2007
  * [91] Adam Kučera and Tomáš Pitner  “Semantic BMS: Allowing usage of building automation data in facility benchmarking”  In _Advanced Engineering Informatics_ 35 Elsevier, 2018, pp. 69–84
  * [92] Ali Kücükavci, Mikki Seidenschnur, Kristoffer Negendahl and Christian Anker Hviid  “Taking advantage of semantic web ontologies and shape constraints for Heating, Cooling and Ventilation Systems”  In _E3S Web of Conferences_ 362, 2022, pp. 04002
  * [93] Seidenschnur Kücükavci, Rasmussen Pauwels and Hviid  “Efficient management and compliance check of HVAC information in the building design phase using semantic web technologies” Accessed on April 16, 2024, 2023  URL: https://www.semantic-web-journal.net/content/efficient-management-and-compliance-check-hvac-information-building-design-phase-using
  * [94] Ville Kukkonen et al.  “An ontology to support flow system descriptions from design to operation of buildings”  In _Automation in Construction_ 134 Elsevier, 2022, pp. 104067
  * [95] Amanda Lazar, Christian Koehler, Theresa Jean Tanenbaum and David H Nguyen  “Why we use and abandon smart devices”  In _Proc. of the ACM Int. Joint Conference on Pervasive and Ubiquitous Computing (UbiComp)_ , 2015, pp. 635–646
  * [96] Sanja Lazarova-Molnar, Hamid Reza Shaker and Nader Mohamed  “Fault detection and diagnosis for smart buildings: State of the art, trends and challenges”  In _Proc. of the 3rd MEC Int. Conference on Big Data and Smart City (ICBDSC)_ , 2016, pp. 1–7
  * [97] Maxime Lefrançois, Jarmo Kalaoja, Takoua Ghariani and Antoine Zimmermann  “The SEAS knowledge model”, 2017
  * [98] Han Li and Tianzhen Hong  “A semantic ontology for representing and quantifying energy flexibility of buildings”  In _Advances in Applied Energy_ 8 Elsevier, 2022, pp. 100113
  * [99] Han Li, Zhe Wang, Tianzhen Hong and Mary Ann Piette  “Energy flexibility of residential buildings: A systematic review of characterization and quantification methods and applications”  In _Advances in Applied Energy_ 3 Elsevier, 2021, pp. 100054
  * [100] Yehong Li et al.  “Enhancing energy management at district and building levels via an EM-KPI ontology”  In _Automation in Construction_ 99 Elsevier, 2019, pp. 152–167
  * [101] Clement Lork et al.  “An ontology-based framework for building energy management with IoT”  In _Electronics_ 8.5 MDPI, 2019, pp. 485
  * [102] Henrik Lund  “Renewable energy systems: a smart energy systems approach to the choice and modeling of 100% renewable solutions”  Academic Press, 2014
  * [103] Na Luo et al.  “Extending the Brick schema to represent metadata of occupants”  In _Automation in Construction_ 139 Elsevier, 2022, pp. 104307
  * [104] Leandro Madrazo, Alvaro Sicilia and Gonzalo Gamboa  “SEMANCO: Semantic tools for carbon reduction in urban planning”  In _Proc. of the 9th European Conference on Product and Process Modelling (ECPPM)_ , 2012
  * [105] Davit Marikyan, Savvas Papagiannidis and Eleftherios Alamanos  “A systematic review of the smart home literature: A user perspective”  In _Technological Forecasting and Social Change_ 138 Elsevier, 2019, pp. 139–154
  * [106] Burstein Martin et al.  “OWL-S: Semantic Markup for Web Services” Accessed on April 16, 2024, 2005  URL: https://www.w3.org/submissions/OWL-S/
  * [107] Dimitris Mavrokapnidis et al.  “A linked-data paradigm for the integration of static and dynamic building data in Digital Twins”  In _Proc. of the 8th ACM Int. Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys)_ , 2021, pp. 369–372
  * [108] Ryan Moats  “URN syntax”  RFC Series, 1997
  * [109] João Moreira et al.  “Towards IoT Platforms’ Integration Semantic Translations between W3C SSN and ETSI SAREF”  In _”SEMANTiCS workshops_ , 2017
  * [110] Ondřej Nehasil, Lucie Dobiášová, Vojtěch Mazanec and Jan Širokỳ  “Versatile AHU fault detection–Design, field validation and practical application”  In _Energy and Buildings_ 237 Elsevier, 2021, pp. 110781
  * [111] Ian Niles and Adam Pease  “Origins of the IEEE standard upper ontology”  In _Working notes of the 17th Int. Joint Conference on Artificial Intelligence (IJCAI) workshop on the IEEE standard upper ontology_ 17, 2001, pp. 4–10
  * [112] James O’Donnell  “Simmodel: A domain data model for whole building energy simulation”, 2012
  * [113] Xavier Ochoa and Erik Duval  “Automatic evaluation of metadata quality in digital repositories”  In _Int. journal on digital libraries_ 10 Springer, 2009, pp. 67–91
  * [114] Open Power System Data  “Data Package Household Data” Accessed on April 16, 2024, 2020  URL: https://data.open-power-system-data.org/household_data/
  * [115] Adrian Taboada Orozco, Amira Mouakher, Imen Ben Sassi and Christophe Nicolle  “An ontology-based thermal comfort management system in smart buildings”  In _Proc. of the 11th Int. Conference on Management of Digital EcoSystems (MEDES)_ , 2019, pp. 300–307
  * [116] Matthew J. Page et al.  “The PRISMA 2020 statement: An updated guideline for reporting systematic reviews”  In _Int. Journal of Surgery_ 88, 2021, pp. 105906
  * [117] Pieter Pauwels  “Supporting decision-making in the building life-cycle using linked building data”  In _Buildings_ 4.3 MDPI, 2014, pp. 549–579
  * [118] Pieter Pauwels, Aaron Costin and Mads Holten Rasmussen  “Knowledge graphs and linked data for the built environment”  In _Industry 4.0 for the Built Environment: Methodologies, Technologies and Skills_ Springer, 2021, pp. 157–183
  * [119] Pieter Pauwels and Walter Terkaj  “EXPRESS to OWL for construction industry: Towards a recommendable and usable ifcOWL ontology”  In _Automation in construction_ 63 Elsevier, 2016, pp. 100–133
  * [120] Pieter Pauwels, Sijie Zhang and Yong-Cheol Lee  “Semantic web technologies in AEC industry: A literature overview”  In _Automation in construction_ 73 Elsevier, 2017, pp. 145–165
  * [121] Pieter Pauwels et al.  “Linked data in architecture and construction”  In _Automation in construction_ 57.2015 Elsevier, 2015, pp. 175–177
  * [122] Joern Ploennigs, Anika Schumann and Freddy Lécué  “Adapting semantic sensor networks for smart building diagnosis”  In _Proc. of the 13th Int. Semantic Web Conference (ISWC)_ , 2014, pp. 308–323
  * [123] Joern Ploennigs, Burkhard Hensel, Henrik Dibowski and Klaus Kabitzsch  “BASont-A modular, adaptive building automation system ontology”  In _Proc. of the 38th Annual Conference on IEEE Industrial Electronics Society (IECON)_ , 2012, pp. 4827–4833
  * [124] Michael J Pratt  “ISO 10303, the STEP standard for product data exchange, and its PLM capabilities”  In _Int. Journal of Product Lifecycle Management_ 1.1 Inderscience Publishers, 2005, pp. 86–94
  * [125] Davy Preuveneers et al.  “Towards an extensible context ontology for ambient intelligence”  In _Proc. of the 2nd Second European Symposium on Ambient Intelligence (EUSAI)_ , 2004, pp. 148–159
  * [126] Marco Pritoni et al.  “Metadata schemas and ontologies for building energy applications: A critical review and use case analysis”  In _Energies_ 14.7 MDPI, 2021, pp. 2024
  * [127] Gilles Privat and A Medvedev  “Guidelines for Modelling with NGSI-LD” Accessed on April 16, 2024, 2021
  * [128] Mads Rasmussen, Pieter Pauwels, Maxime Lefrançois and Georg Schneider  “Building Topology Ontology” Accessed on April 16, 2024, 2021  URL: https://w3c-lbd-cg.github.io/bot/
  * [129] Mads Holten Rasmussen, Maxime Lefrançois, Georg Ferdinand Schneider and Pieter Pauwels  “BOT: The building topology ontology of the W3C linked building data group”  In _Semantic Web_ 12.1 IOS Press, 2021, pp. 143–161
  * [130] Christian Reinisch, Mario J Kofler and Wolfgang Kastner  “ThinkHome: A smart home as digital ecosystem”  In _Proc. of the 4th IEEE Int. Conference on Digital Ecosystems and Technologies (DEST)_ , 2010, pp. 256–261
  * [131] Hajo Rijgersberg, Mark Van Assem and Jan Top  “Ontology of units of measure and related concepts”  In _Semantic Web_ 4.1 IOS Press, 2013, pp. 3–13
  * [132] Djamel Saba, Youcef Sahli and Abdelkader Hadidi  “An ontology based energy management for smart home”  In _Sustainable Computing: Informatics and Systems_ 31 Elsevier, 2021, pp. 100591
  * [133] Djamel Saba et al.  “Development of new ontological solution for an energy intelligent management in Adrar city”  In _Sustainable Computing: Informatics and Systems_ 21 Elsevier, 2019, pp. 189–203
  * [134] Khouloud Salameh, Richard Chbeir and Haritza Camblong  “SSG: An ontology-based information model for smart grids”  In _Transactions on Large-Scale Data-and Knowledge-Centered Systems XL_ Springer, 2019, pp. 94–124
  * [135] Daniel Schachinger, Wolfgang Kastner and Stefan Gaida  “Ontology-based abstraction layer for smart grid interaction in building energy management systems”  In _Proc. of the IEEE Int. energy conference (ENERGYCON)_ , 2016, pp. 1–6
  * [136] Georg Ferdinand Schneider  “Towards aligning domain ontologies with the building topology ontology”  In _Proc. of the 5th Linked Data in Architecture and Construction Workshop (LDAC 2017)_ , 2017
  * [137] Nazaraf Shah, Kuo-Ming Chao, Tomasz Zlamaniec and Adriana Matei  “Ontology for Home Energy Management Domain”  In _Proc. of the Digital Information and Communication Technology and Its Applications (DICTAP)_ , 2011, pp. 337–347
  * [138] Wenchi Shou, Jun Wang, Xiangyu Wang and Heap Yih Chong  “A comparative review of building information modelling implementation in building and infrastructure industries”  In _Archives of computational methods in engineering_ 22 Springer, 2015, pp. 291–308
  * [139] Pierluigi Siano  “Demand response and smart grids—A survey”  In _Renewable and sustainable energy reviews_ 30 Elsevier, 2014, pp. 461–478
  * [140] Smart Electric Power Alliance  “Smart Grid Ontology” Accessed on April 16, 2024  URL: https://sepapower.org/smart-grid-ontology/
  * [141] Manu Sporny et al.  “JSON-LD 1.1”  In _W3C Recommendation, Jul_ , 2020
  * [142] Stap and Daniele  “Ontology ’A CIM Profile for Smart Grids”’ Accessed on April 16, 2024  URL: https://ontology.tno.nl/cerise/cim-profile/
  * [143] Thanos G Stavropoulos, Dimitris Vrakas, Danai Vlachava and Nick Bassiliades  “BOnSAI: a smart building ontology for ambient intelligence”  In _Proc. of the 2nd Int. Conference on Web Intelligence, Mining and Semantics (WIMS)_ , 2012, pp. 1–12
  * [144] Rudi Studer, V Richard Benjamins and Dieter Fensel  “Knowledge engineering: Principles and methods”  In _Data & knowledge engineering_ 25.1-2 Elsevier, 1998, pp. 161–197
  * [145] Ruiji Sun, Carlo Duarte Roa, Paul Raftery and Gabe Fierro  “Enabling Portable and Reproducible Long-term Thermal Comfort Evaluation with Brick Schema and Mortar Testbed”, 2022
  * [146] H Tarumi  “Text of architecture environment: design of thermal and air”  In _Inoue Shoin_ , 2007
  * [147] Utku Tefek, Ertem Esiner, Carmen Cheh and Daisuke Mashima  “A Smart Grid Ontology: Vulnerabilities, Attacks, and Security Policies”  In _Proc. of the 11th IEEE Conference on Communications and Network Security (CNS)_ , 2023, pp. 1–6
  * [148] Walter Terkaj and Pieter Pauwels  “A method to generate a modular ifcOWL ontology”  In _Proc. of the 8th Int. Workshop on Formal Ontologies meet Industry (FOMI)_ 2050, 2017
  * [149] Walter Terkaj, Georg Ferdinand Schneider and Pieter Pauwels  “Reusing domain ontologies in linked building data: the case of building automation and control”  In _Proc. of the 8th Int. Workshop on Formal Ontologies Meet Industry (FOMI)_ 2050, 2017
  * [150] James Hendler Tim Berners-Lee and Ora Lassila  “The Semantic Web” Accessed on April 16, 2024, 2001  URL: https://www.scientificamerican.com/article/the-semantic-web/
  * [151] Maria Lorena Tuballa and Michael Lochinvar Abundo  “A review of the development of Smart Grid technologies”  In _Renewable and Sustainable Energy Reviews_ 59 Elsevier, 2016, pp. 710–725
  * [152] JPC Verhoosel, DCF Rothengatter, FJ Rumph and MJ Konsman  “An ontology for modeling flexibility in smart grid energy management”  In _Proc. of the eWork and eBusiness in Architecture, Engineering and Construction in 9th European Conference on Product and Process Modelling (ECPPM)_ , 2012, pp. 931–938
  * [153] Wallin and Hammar  “RealEstateCore Full” Accessed on April 16, 2024, 2020  URL: https://doc.realestatecore.io/3.2/full.html
  * [154] Roderick Weerdt, Victor Boer, Laura Daniele and Barry Nouwt  “Validating SAREF in a smart home environment”  In _Proc. of the 14th Int. Conference on Metadata and Semantics Research (MTSR)_ , 2020, pp. 35–46
  * [155] Roderick Van Der Weerdt et al.  “Making heterogeneous smart home data interoperable with the SAREF ontology”  In _Int. Journal of Metadata, Semantics and Ontologies_ 15.4 Inderscience Publishers (IEL), 2021, pp. 280–293
  * [156] World Wide Web Consortium (W3C)  “Linked Data Glossary” Accessed on April 16, 2024, 2013  URL: https://www.w3.org/TR/ld-glossary
  * [157] Fu Xiao and Cheng Fan  “Data mining in building automation system for improving building operational performance”  In _Energy and buildings_ 75 Elsevier, 2014, pp. 109–118
  * [158] Martin Žáček and Michal Janošek  “SBOnto: Ontology of smart building”  In _Far East Journal of Electronics and Communications_ 17.5, 2017, pp. 1101–1109
  * [159] Yun-Yi Zhang, Zhen-Zhong Hu, Jia-Rui Lin and Jian-Ping Zhang  “Linking data model and formula to automate KPI calculation for building performance benchmarking”  In _Energy Reports_ 7 Elsevier, 2021, pp. 1326–1337
  * [160] Qunzhi Zhou, Sreedhar Natarajan, Yogesh Simmhan and Viktor Prasanna  “Semantic information modeling for emerging applications in smart grid”  In _Proc. of the 9th Int. Conference on Information Technology-New Generations (ITNG)_ , 2012, pp. 775–782


# Gallai’s path decomposition conjecture for cartesian product of graphs
(II)111Research supported by NSFC (No.12061073)

Xiaohong Chen222Email<EMAIL_ADDRESS>(X. Chen), Baoyindureng
Wu333Corresponding author. Email<EMAIL_ADDRESS>(B. Wu)
College of Mathematics and System Science, Xinjiang University
Urumqi 830046, P.R.China

Abstract: Let $G$ be a graph of order $n$. A path decomposition $\mathcal{P}$
of $G$ is a collection of edge-disjoint paths that covers all the edges of
$G$. Let $p(G)$ denote the minimum number of paths needed in a path
decomposition of $G$. Gallai conjectured that if $G$ is connected, then
$p(G)\leq\lceil\frac{n}{2}\rceil$. In this paper, we prove that Gallai’s path
decomposition conjecture holds for the cartesian product $G\Box H$, where $H$
is any graph and $G$ is a unicyclic graph or a bicyclic graph.
Keywords: Cycle; Decomposition; Gallai’s conjecture; Cartesian product

##  1 Introduction

All graphs considered here are finite, undirected and simple. We refer to [5]
for unexplained terminology and notation. Let $G=(V(G),E(G))$ be a graph. The
order $|V(G)|$ and size $|E(G)|$ are denoted by $n(G)$ and $e(G)$,
respectively. The degree and the neighborhood of a vertex $v$ are denoted by
$d_{G}(v)$ and $N_{G}(v)$, respectively. A vertex is called odd or even
depending on whether its degree is odd or even, respectively. A graph in which
every vertex is odd or even is called an odd graph or an even graph. The
number of odd vertices and even vertices of $G$ are denoted by $n_{o}(G)$ and
$n_{e}(G)$, respectively. Let $S\subseteq V(G)$. The subgraph induced by $S$,
denoted by $G[S]$, is the graph with $S$ as its vertex set, in which two
vertices are adjacent if and only if they are adjacent in $G$. The union of
simple graphs $G$ and $H$ is the graph $G\cup H$ with vertex set $V(G)\cup
V(H)$ and edge set $E(G)\cup E(H)$. We use $G+uv$ to denote the graph that
arises from $G$ by adding an edge $uv\notin E(G)$, where $u,v\in V(G)$.
Similarly, $G-u$ is a graph that arises from $G$ by deleting the vertex $u\in
V(G)$. As usual, we use $P_{n}$ and $C_{n}$ to denote the path and cycle of
order $n$, respectively.

A path decomposition $\mathcal{P}$ of a graph $G$ is a collection of edge-
disjoint paths that covers all the edges of $G$. We use $p(G)$ to denote the
minimum number of paths needed for a path decomposition of $G$. Erdős asked
that what is the minimum number of paths into which every connected graph can
be decomposed. As a response to the question of Erdős, Gallai made the
following conjecture:

######  Conjecture 1.1 ([28]).

For any connected graph $G$ of order $n$, then
$p(G)\leq\lceil\frac{n}{2}\rceil$.

The assertion of Gallai’s conjecture is sharp if it is true: If $G$ is a graph
in which every vertex has odd degree, then in any path decomposition of $G$
each vertex must be the end vertex of some path, and so at least
$\lceil\frac{n}{2}\rceil$ paths are required. In 1968, Lovász [28] proved that
every graph of order $n$ can be decomposed into at most $\frac{n}{2}$ paths
and cycles. Moreover, he proved that if a connected graph $G$ with $n$
vertices has at most one even vertex, then $p(G)\leq\lceil\frac{n}{2}\rceil$.
In 1996, Pyber [30] extended Lovász’s result by proving that Conjecture 1.1
holds for graphs whose each cycle contains a vertex of odd degree. In 1980,
Donald [14] showed that if $G$ is allowed to be disconnected, then
$p(G)\leq\lfloor\frac{3n}{4}\rfloor$, which was improved to
$\lfloor\frac{2n}{3}\rfloor$ independently by Dean and Kouider [13] and Yan
[33].

Furthermore, the Conjecture 1.1 was verified for several classes of graphs.
Fan [17] proved that the conjecture is true if each block of the even subgraph
is a triangle-free graph with maximum degree at most three. Botler and
Sambinelli [8] generalized Fan’s result in [17]. Also, Botler and Jiménez [6]
showed Conjecture 1.1 is ture for a family of even regular graphs with a high
girth condition. Harding and McGuinness[20] proved that for any simple graph
$G$ having girth $g\geq 4$, there is a path decomposition of $G$ having at
most $\frac{n_{o}(G)}{2}+\lfloor(\frac{g+1}{2g})n_{e}(G)\rfloor$ paths.
Recently, Chu, Fan and Zhou [12] proved that for any triangle-free graph $G$,
$p(G)\leq\lfloor\frac{3n}{5}\rfloor$. More results regarding Conjecture 1.1
can be found in [4, 7, 9, 11, 17, 18, 24]. But in general, it is still open.

The cartesian product of simple graphs $G$ and $H$ is the graph $G\Box H$
whose vertex set is $V(G)\times V(H)$ and whose edge set is the set of all
pairs $(u_{1},v_{1})(u_{2},v_{2})$ such that either $u_{1}u_{2}\in E(G)$ and
$v_{1}=v_{2}$, or $v_{1}v_{2}\in E(H)$ and $u_{1}=u_{2}$. Every connected
graph has a unique factorization under this graph product [32], and this
factorization can be found in linear time and space [21]. In 2016, Jeevadoss
and Muthusamy [23] shown that the cartesian product of complete graphs can be
decompose to $P_{5}$ and $C_{4}$. In 2021, Ezhilarasi and Muthusamy [16]
proved that cartesian product of complete graphs can be decompose to $P_{5}$
and $K_{1,4}$. In 2018, Oyewumi, Akwu and Azer [29] determined a path
decomposition of cartesian product of $P_{m}$ and $C_{n}$ with $p(P_{m}\Box
C_{n})=n$. In 2023, Chen and Wu [10] extended the above result further and
proved the following theorems.

######  Theorem 1.2 ([10]).

Let $m$ be an integer $m\geq 2$ and $H$ be a connected graph of order $n$. If
$G=P_{m}\Box H$, then $p(G)\leq\frac{mn}{2}$.

######  Theorem 1.3 ([10]).

Let $G$ be a connected graph of order $m\geq 2$ and $H$ be a connected graph
of order $n$. If $p(G)=\frac{n_{o}(G)}{2}$, then $p(G\Box H)\leq\frac{mn}{2}$.

In addition, for other interesting results on cartesian product of graphs can
be found in [1, 19, 22, 25, 31].

A unicyclic graph is a connected graph with $n$ vertices and $n$ edges. A
bicyclic graph is a connected graph with $n$ vertices and $n+1$ edges. We
refer to [2, 3, 15, 26, 27] for some recent results on unicyclic and bicyclic
graphs. In this paper, we prove that Gallai’s path decomposition conjecture
holds for the cartesian product of a general graph and a unicyclic graph, a
general graph and a bicyclic graph, respectively.

##  2 Notation

In this section, we will introduce some notations to be used in this paper.
Let $u,v\in V(G)$ and $P_{u,v}$ be a path of $G$ with ends $u$ and $v$. We
call $u$ is an odd end vertex of $P_{u,v}$ if $u$ is odd in $G$, otherwise,
$u$ is an even end vertex of $P_{u,v}$. If both $u$ and $v$ are odd end
vertices in $G$, we call $P_{u,v}$ is an odd-odd path. If both $u$ and $v$ are
even end vertices in $G$, then $P_{u,v}$ is an even-even path. If the degree
of $u$ and $v$ have different parity, we call $P_{u,v}$ is an odd-even path.

A sequence of vertices and edges $W:=v_{1}e_{1}v_{2}...v_{l}e_{l}v_{l+1}$ is
called a trail if $e_{i}=v_{i}v_{i+1}\in E(W)$ for each
$i\in\\{1,2,\cdots,l\\}$ and $e_{i}\neq e_{j}$ if $i\neq j$. If
$v_{1}=v_{l+1}$, then $W$ is a closed trail. A trail
$W:=v_{1}P_{v_{1},v_{2}}v_{2}...v_{r}P_{v_{r},v_{r+1}}v_{r+1}$ is called a
$\mathcal{P}$-$r$-trail if $W$ is the union of $r$ edge disjoint paths
$P_{v_{1},v_{2}}...P_{v_{r},v_{r+1}}$ of $\mathcal{P}$, and $v_{i}\neq v_{j}$
if $i\neq j$. If $v_{1}=v_{r+1}$, then $W$ is $\mathcal{P}$-$r$-closed-trail.

Let $P_{m}$ be a path with $V(P_{m})=\\{u_{1},u_{2},\cdots,u_{m}\\}$. Some
internal vertices of $P_{m}$ are called virtual, and the remaining ones are
called real. Note that the ends of the path must be real. Such a path is
called a virtual-real path. Similarly, $C_{m}$ be a cycle with
$V(C_{m})=\\{u_{1},u_{2},\cdots,u_{m}\\}$. Some vertices of $C_{m}$ are called
virtual, and the remaining ones are called real. Note that the number of real
vertices on $C_{m}$ is at least three. Such a cycle is called a virtual-real
cycle. The cartesian product of a virtual-real path $P_{m}$ (or virtual-real
cycle $C_{m}$) and a graph $H$ is defined as the graph with $V(P_{m}\boxdot
H)=V(P_{m})\times V(H)$ (or $V(C_{m}\boxdot H)=V(C_{m})\times V(H)$), in which
for any $v\in V(H)$, $\\{(u_{i},v):\ 1\leq i\leq m\\}$ induces $P_{m}$ (or
$C_{m}$), for each $i\in\\{1,\ldots,m\\}$, $\\{u_{i}\\}\times V(H)$ induces a
graph isomorphic to $H$ if $u_{i}$ is real, and otherwise, $\\{u_{i}\\}\times
V(H)$ is an independent set.

The following lemma presented a path decomposition for a graph and was proved
in [10]. We restate it as:

######  Lemma 2.1 ([10]).

For any connected graph $H$, there exists a path decomposition
$\mathcal{P}(H)$ of the edges of $H$, such that:

(1) each odd vertex is the end vertex of exactly one path of $\mathcal{P}(H)$;

(2) each even vertex is the end vertex of exactly two path of
$\mathcal{P}(H)$;

(3) $|\mathcal{P}(H)|=\frac{n_{o}(H)}{2}+n_{e}(H)$.

Let $\mathcal{P}(H)$ be a path decomposition of $H$ as given in the Lemma 2.1.
Now the $\mathcal{P}(H)$ can be classified into odd-odd, even-even, odd-even
(or even-odd) paths respectively. We denote the number of odd end vertices of
odd-odd paths in $\mathcal{P}(H)$ as $n_{o}^{1}(H)$, and the number of odd end
vertices of odd-even paths as $n_{o}^{2}(H)$. Clearly,
$n_{o}^{1}(H)+n_{o}^{2}(H)=n_{o}(H)$. For any even-even path, it is either on
a $\mathcal{P}$-$r$-trail or on a $\mathcal{P}$-$r$-closed-trail. We denote
the number of even end vertices of even-even paths on the
$\mathcal{P}$-$r$-trail in $\mathcal{P}(H)$ as $n_{e}^{1}(H)$, and the number
of even end vertices of even-even paths on the $\mathcal{P}$-$r$-closed-trail
in $\mathcal{P}(H)$ as $n_{e}^{2}(H)$. Clearly,
$n_{e}^{1}(H)+n_{e}^{2}(H)=n_{e}(H)$.

Based on the above facts, it follows that $H$ can be decomposed into some odd-
odd paths, $\mathcal{P}$-$r$-trail and $\mathcal{P}$-$r$-closed-trail. Let $v$
be any vertex in $H$. It is assigned to be real on the path in
$\mathcal{P}(H)$ with $v$ as an end vertex, and is assigned to virtual for the
remaining paths containing it. Then
$2t_{1}+\sum_{i=1}^{t_{2}}(r_{i}+1)+\sum_{j=1}^{t_{3}}r_{j}=n(H)$, where
$t_{1}=\frac{n_{o}^{1}(H)}{2}$, $t_{2}=\frac{n_{o}^{2}(H)}{2}$, and $t_{3}$ is
the number of $\mathcal{P}$-$r$-closed-trails of $\mathcal{P}(H)$. Two
examples are shown in Fig. 1. Let $H_{1}$ be the union of odd-odd paths of
$\mathcal{P}(H)$, $H_{2}$ be the union of $\mathcal{P}$-$r$-trails of
$\mathcal{P}(H)$ and $H_{3}$ be the union of $\mathcal{P}$-$r$-closed-trail of
$\mathcal{P}(H)$. It obvious that $E(H)=\bigcup_{i=1}^{3}E(H_{i})$. Hence,
$E(G\Box H)=\bigcup_{i=1}^{3}E(G\boxdot H_{i})$.

Fig. 1. $(a)$ represents a path decomposition of $K_{4}$ that satisfies Lemma
2.1, where $P_{u_{1},u_{3}}=u_{1}u_{4}u_{2}u_{3}$ that $u_{1}$ and $u_{3}$ are
real and $u_{2}$ and $u_{4}$ are virtual, and
$P_{u_{2},u_{4}}=u_{2}u_{1}u_{3}u_{4}$ that $u_{2}$ and $u_{4}$ are real and
$u_{1}$ and $u_{3}$ is virtual. $(b)$ represents a path decomposition of
$K_{5}$ that satisfies Lemma 2.1, for each $i\in\\{1,2,3,4,5\\}$,
$P_{u_{i},u_{i+1}}=u_{i}u_{i-1}u_{i+1}$ where $u_{i}$ and $u_{i+1}$ are real
and $u_{i-1}$ is virtual and the subscripts are taken modular $5$.

In this paper we also use the following lemma.

######  Lemma 2.2 ([10]).

If $G^{\prime}$ be a graph obtained from a graph $G$ by subdividing an edge,
then $p(G^{\prime})=p(G)$.

##  3 Some auxiliary results

In this section we will use the path decomposition of cartesian product of
$P_{m}$ and a connected graph $H$ given in [10], which is as follows.

Let $P_{m}:=u_{1}u_{2}\cdots u_{m}$ and $V(H)=\\{v_{1},v_{2},\cdots,v_{n}\\}$.
For the graph $G=P_{m}\Box H$, let
$U_{i}=\\{(u_{i},v_{j}):j\in\\{1,2,\cdots,n\\}\\}$ where
$i\in\\{1,2,\cdots,m\\}$. Let $\mathcal{P}(H)$ be a path decomposition of $H$
as described in Lemma 2.1 and
$\mathcal{P}_{i}=\\{P^{i}:V(P^{i})=\\{(u_{i},v):v\in
V(P),P\in\mathcal{P}(H)\\}\\}$, where $i\in\\{1,2,\cdots,m\\}$.

For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $P_{m}\boxdot
P_{y_{1},y_{2}}$ can be decomposed into $m$ paths as follows:

If $m$ is even, then

$\mathcal{P}_{11}=\\{\bigcup_{i=1}^{m}P_{y_{1},y_{2}}^{i}\\}\cup\\{(u_{i},y_{1})(u_{i+1},y_{1}):i\in\\{2,4,\cdots,m-2\\}\\}\cup\\{(u_{i},y_{2})(u_{i+1},y_{2}):i\in\\{1,3,\cdots,m-1\\}\\}$,

$\mathcal{P}_{12}=\\{(u_{i},y_{1})(u_{i+1},y_{1})\\}$ for each
$i\in\\{1,3,\cdots,m-1\\}$,

$\mathcal{P}_{13}=\\{(u_{i},y_{2})(u_{i+1},y_{2})\\}$ for each
$i\in\\{2,4,\cdots,m-2\\}$.

If $m$ is odd, then

$\mathcal{P}_{11}=\\{\bigcup_{i=1}^{m}P_{y_{1},y_{2}}^{i}\\}\cup\\{(u_{i},y_{1})(u_{i+1},y_{1}):i\in\\{2,4,\cdots,m-1\\}\\}\cup\\{(u_{i},y_{2})(u_{i+1},y_{2}):i\in\\{1,3,\cdots,m-2\\}\\}$,

$\mathcal{P}_{12}=\\{(u_{i},y_{1})(u_{i+1},y_{1})\\}$ for each
$i\in\\{1,3,\cdots,m-2\\}$,

$\mathcal{P}_{13}=\\{(u_{i},y_{2})(u_{i+1},y_{2})\\}$ for each
$i\in\\{2,4,\cdots,m-1\\}$.

For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, $P_{m}\boxdot W_{1}$ can be
decomposed into $m+r-1$ paths as follows:

If $m$ is even

$\mathcal{P}_{21}=\\{\bigcup_{i=1}^{m}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{i},y_{j})(u_{i+1},y_{j}):i\in\\{2,4,\cdots,m-2\\}\\}\cup\\{(u_{i},y_{j+1})(u_{i+1},y_{j+1}):i\in\\{1,3,\cdots,m-1\\}\\}$
for each $j\in\\{1,\ldots,r\\}$,

$\mathcal{P}_{22}=\\{(u_{i},y_{1})(u_{i+1},y_{1})\\}$ for each
$i\in\\{1,3,\cdots,m-1\\}$,

$\mathcal{P}_{23}=\\{(u_{i},y_{r+1})(u_{i+1},y_{r+1})\\}$ for each
$i\in\\{2,4,\cdots,m-2\\}$.

If $m$ is odd

$\mathcal{P}_{21}=\\{\bigcup_{i=1}^{m}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{i},y_{j})(u_{i+1},y_{j}):i\in\\{2,4,\cdots,m-1\\}\\}\cup\\{(u_{i},y_{j+1})(u_{i+1},y_{j+1}):i\in\\{1,3,\cdots,m-2\\}\\}$
for each $j\in\\{1,\ldots,r\\}$,

$\mathcal{P}_{22}=\\{(u_{i},y_{1})(u_{i+1},y_{1})\\}$ for each
$i\in\\{1,3,\cdots,m-2\\}$,

$\mathcal{P}_{23}=\\{(u_{i},y_{r+1})(u_{i+1},y_{r+1})\\}$ for each
$i\in\\{2,4,\cdots,m-1\\}$.

For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, $P_{m}\boxdot W_{2}$ can be
decomposed into $r$ paths as follows:

If $m$ is even, then

$\mathcal{P}_{31}=\\{\bigcup_{i=1}^{m}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{i},y_{j})(u_{i+1},y_{j}):i\in\\{2,4,\cdots,m-2\\}\\}\cup\\{(u_{i},y_{j+1})(u_{i+1},y_{j+1}):i\in\\{1,3,\cdots,m-1\\}\\}$
for each $j\in\\{1,\ldots,r\\}$.

If $m$ is odd, then

$\mathcal{P}_{31}=\\{\bigcup_{i=1}^{m}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{i},y_{j})(u_{i+1},y_{j}):i\in\\{2,4,\cdots,m-1\\}\\}\cup\\{(u_{i},y_{j+1})(u_{i+1},y_{j+1}):i\in\\{1,3,\cdots,m-2\\}\\}$
for each $j\in\\{1,\cdots,r\\}$.

To conclude the above, $G$ has a path decomposition $\mathcal{P}(G)$ with

$\displaystyle p(G)$ $\displaystyle\leq$ $\displaystyle p(P_{m}\boxdot
H_{1})+p(P_{m}\boxdot H_{2})+p(P_{m}\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle
m\frac{n_{o}^{1}(H)}{2}+m\frac{n_{o}^{2}(H)}{2}+n_{e}^{1}(H)+n_{e}^{2}(H)$
$\displaystyle=$ $\displaystyle m\frac{n_{o}(H)}{2}+n_{e}(H).$

Fig. 2

Let $\mathcal{A}$ be the family of all graphs, which are obtained from $A$ (in
Fig. 2) by identifying a vertex $x\in\\{u_{2},u_{3},v_{2},v_{3}\\}$ with an
end vertex of a separate path $P$. Let $\mathcal{B}$ be the family of all
graphs, which are obtained from $B$ (in Fig. 2) by identifying a vertex
$x\in\\{u_{4},v_{4}\\}$ with an end vertex of a separate path $P$. Let
$\mathcal{F}$ be the family of all graphs, which are obtained from $F$ (in
Fig. 2) by identifying a vertex $x\in\\{u_{3},v_{3}\\}$ with an end vertex of
a separate path $P$. Let $\mathcal{G}$ be the family of all graphs, which are
obtained from a path $P$ by identifying each end vertices of $P$ with a vertex
of a $C_{3}$. By a similar argument as in above, we can obtain the following
lemmas.

######  Lemma 3.1.

Let $G$ be a connected graph of order $m$ and $H$ be a connected graph of
order $n$. If $G\in\mathcal{A}$, then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $G=P_{m}+\\{u_{1}u_{3},u_{3}u_{5}\\}$ where $P_{m}=u_{1}u_{2}\cdots
u_{m}$, $m\geq 5$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $G\boxdot
P_{y_{1},y_{2}}$ can be decomposed into $m$ paths as follows:

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),\\\
(u_{4},y_{1})(u_{3},y_{1})(u_{5},y_{1})\\}\cup\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{2})(u_{3},y_{2}),(u_{4},y_{2})(u_{5},y_{2})\\}\\}\cup\\{(u_{1},y_{2})(u_{3},y_{2})(u_{2},y_{2}),\\\
(u_{4},y_{2})(u_{5},y_{2})(u_{3},y_{2})\\}$.

Then $p(G\boxdot H_{1})\leq\sum_{i=1}^{t_{1}}p(G\boxdot
P_{y_{1_{i}},y_{2_{i}}})=\sum_{i=1}^{t_{1}}p(G\Box
P_{2})\leq\frac{mn_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, $G\boxdot W_{1}$ can be
decomposed into $m+2r-2$ paths as follows:

$\mathcal{P}_{24}=\\{(u_{1},y_{j})(u_{3},y_{j})(u_{5},y_{j})\\}$ for each
$j\in\\{2,3,\cdots,r\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),\\\
(u_{4},y_{1})(u_{3},y_{1})(u_{5},y_{1})\\}\cup\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{r+1})(u_{3},y_{r+1}),(u_{4},y_{r+1})(u_{5},y_{r+1})\\}\\}\cup\\{(u_{1},y_{r+1})\\\
(u_{3},y_{r+1})(u_{2},y_{r+1}),(u_{4},y_{r+1})(u_{5},y_{r+1})(u_{3},y_{r+1})\\}\cup\mathcal{P}_{24}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(m+2r_{i}-2)\leq\sum_{i=1}^{t_{2}}\frac{m(r_{i}+1)}{2}\leq\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

(3) For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, $G\boxdot W_{2}$ can be
decomposed into $2r$ paths as follows:

$\mathcal{P}_{32}=\\{(u_{1},y_{j})(u_{3},y_{j})(u_{5},y_{j})\\}$ for each
$j\in\\{1,2,\cdots,r\\}$.

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}2r_{i}\leq\frac{mn_{e}^{2}(H)}{2}$ where
$r_{i}$ is the number of paths on $W_{2_{i}}$.

Combining the above, we conclude that there is a path decomposition
$\mathcal{P}(G\Box H)$ of graph $G\Box H$ with

$\displaystyle p(G\Box H)$ $\displaystyle\leq$ $\displaystyle p(G\boxdot
H_{1})+p(G\boxdot H_{2})+p(G\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{mn_{o}^{1}(H)}{2}+\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{mn_{e}^{2}(H)}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

######  Lemma 3.2.

Let $G$ be a connected graph of order $m$ and $H$ be a connected graph of
order $n$. If $G\in\mathcal{B}$, then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $G=P_{m}+\\{u_{1}u_{4},u_{2}u_{5}\\}$ where $P_{m}=u_{1}u_{2}\cdots
u_{m}$, $m\geq 5$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $G\boxdot
P_{y_{1},y_{2}}$ can be decomposed into $m-2$ paths as follows:

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{3},y_{1})(u_{4},y_{1})(u_{1},y_{1})\\\
(u_{2},y_{1})(u_{5},y_{1})\\}\cup\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{2})(u_{3},y_{2}),(u_{4},y_{2})(u_{5},y_{2})\\}\\}\cup\\{(u_{1},y_{2})(u_{4},y_{2})(u_{5},y_{2})(u_{2},y_{2})(u_{3},y_{2})\\}$.

Then $p(G\boxdot H_{1})=\sum_{i=1}^{t_{1}}p(G\boxdot
P_{y_{1_{i}},y_{2_{i}}})=\frac{n_{o}^{1}(H)}{2}p(G\Box
P_{2})\leq\frac{mn_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, we will consider the two
cases as follows:

Case 1. If $m\geq 6$, then $G\boxdot W_{1}$ can be decomposed into $m+3r-5$
paths as follows:

$\mathcal{P}_{24}=\\{(u_{1},y_{j})(u_{4},y_{j}),(u_{2},y_{j})(u_{5},y_{j})\\}$
for each $j\in\\{2,3,\cdots,r\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{3},y_{1})(u_{4},y_{1})(u_{1},y_{1})$
$(u_{2},y_{1})(u_{5},y_{1})\\}\cup\\{\mathcal{P}_{23}\setminus\\{(u_{2},y_{r+1})(u_{3},y_{r+1}),(u_{4},y_{r+1})(u_{5},y_{r+1})\\}\\}\cup\\{(u_{1},y_{r+1})(u_{4},y_{r+1})(u_{5},y_{r+1})$
$(u_{2},y_{r+1})(u_{3},y_{r+1})\\}\cup\mathcal{P}_{24}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(m+3r_{i}-5)\leq\sum_{i=1}^{t_{2}}\frac{m(r_{i}+1)}{2}\leq\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

Case 2. If $m=5$, then $P_{m}\boxdot W_{1}$ can be decomposed into at most
$2r+2$ paths as follows:

When $r$ is even,
$\mathcal{P}_{24}=\\{(u_{1},y_{r})(u_{4},y_{r}),(u_{2},y_{r})(u_{5},y_{r})\\}\cup\\{(u_{2},y_{j})(u_{5},y_{j})P^{5}_{y_{j},y_{j+1}}(u_{5},y_{j+1})\\\
(u_{2},y_{j+1})\\}\cup\\{(u_{4},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{4},y_{j+1})\\}$
for each $j\in\\{2,4,\cdots,r-2\\}$.

When $r$ is odd,
$\mathcal{P}_{24}=\\{(u_{2},y_{j})(u_{5},y_{j})P^{5}_{y_{j},y_{j+1}}(u_{5},y_{j+1})(u_{2},y_{j+1})\\}\cup\\{(u_{4},y_{j})(u_{1},y_{j})\\\
P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{4},y_{j+1})\\}$ for each
$j\in\\{2,4,\cdots,r-1\\}$.

Let $\mathcal{P^{\prime}}_{21}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{21}\ and\ Q\in\mathcal{P}_{24}\\}$.

Hence, $\mathcal{P}(G\boxdot
W_{1})=\mathcal{P^{\prime}}_{21}\cup\mathcal{P}_{24}\cup\\{(u_{3},y_{1})(u_{4},y_{1})(u_{1},y_{1})(u_{2},y_{1})(u_{5},y_{1})\\}\cup\\{(u_{1},y_{r+1})\\\
(u_{4},y_{r+1})(u_{5},y_{r+1})(u_{2},y_{r+1})(u_{3},y_{r+1})\\}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(2r_{i}+2)\leq\sum_{i=1}^{t_{2}}\frac{5(r_{i}+1))}{2}=\frac{5}{2}(n_{o}^{2}(H)+n_{e}^{1}(H))$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

(3) For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, we will consider the two cases
as follows:

Case 1. If $m\geq 6$, then $P_{m}\boxdot W_{2}$ can be decomposed into $3r$
paths as follows:

$\mathcal{P}_{32}=\\{(u_{1},y_{j})(u_{4},y_{j}),(u_{2},y_{j})(u_{5},y_{j})\\}$
for each $j\in\\{1,3,\cdots,r\\}$.

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}3r_{i}\leq m\frac{n_{e}^{2}(H)}{2}$ where
$r_{i}$ is the number of paths on $W_{2_{i}}$.

Case 2. If $m=5$, then $P_{m}\boxdot W_{2}$ can be decomposed into at most
$2r+1$ paths as follows:

When $r$ is odd,
$\mathcal{P}_{32}=\\{(u_{1},y_{r})(u_{4},y_{r}),(u_{2},y_{r})(u_{5},y_{r})\\}\cup\\{(u_{2},y_{j})(u_{5},y_{j})P^{5}_{y_{j},y_{j+1}}(u_{5},y_{j+1})\\\
(u_{2},y_{j+1})\\}\cup\\{(u_{4},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{4},y_{j+1})\\}$
for each $j\in\\{1,3,\cdots,r-2\\}$.

When $r$ is even,
$\mathcal{P}_{32}=\\{(u_{2},y_{j})(u_{5},y_{j})P^{5}_{y_{j},y_{j+1}}(u_{5},y_{j+1})(u_{2},y_{j+1})\\}\cup\\{(u_{4},y_{j})(u_{1},y_{j})\\\
P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{4},y_{j+1})\\}$ for each
$j\in\\{1,3,\cdots,r-1\\}$.

Let $\mathcal{P^{\prime}}_{31}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{31}\ and\ Q\in\mathcal{P}_{32}\\}$.

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P^{\prime}}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}(2r_{i}+1)\leq\frac{mn_{e}^{2}(H)}{2}$ where
$r_{i}$ is the number of paths on $W_{2_{i}}$.

Summing up the above, $G\Box H$ has a path decomposition $\mathcal{P}(G\Box
H)$ with

$\displaystyle p(G\Box H)$ $\displaystyle\leq$ $\displaystyle p(G\boxdot
H_{1})+p(G\boxdot H_{2})+p(G\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{mn_{o}^{1}(H)}{2}+\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{mn_{e}^{2}(H)}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

######  Lemma 3.3.

Let $G$ be a connected graph of order $m$ and $H$ be a connected graph of
order $n$. If $G\in\mathcal{F}$, then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $G=P_{m}+\\{u_{1}u_{3},u_{2}u_{4}\\}$ where $P_{m}=u_{1}u_{2}\cdots u_{m}$
and $m\geq 4$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $G\boxdot
P_{y_{1},y_{2}}$ can be decomposed into $m$ paths as follows:

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{1},y_{1})(u_{3},y_{1})(u_{4},y_{1}),\\\
(u_{1},y_{1})(u_{2},y_{1})(u_{4},y_{1})\\}\cup\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{2})(u_{3},y_{2})\\}\\}\cup\\{(u_{1},y_{2})(u_{3},y_{2})(u_{2},y_{2})(u_{4},y_{2})\\}$.

Then $p(G\boxdot H_{1})\leq\sum_{i=1}^{t_{1}}p(G\boxdot
P_{y_{1_{i}},y_{2_{i}}})=\sum_{i=1}^{t_{1}}p(G\Box
P_{2})\leq\sum_{i=1}^{t_{1}}m\leq\frac{mn_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, we will consider the three
cases as follows:

Case 1. If $m\geq 6$, then $P_{m}\boxdot W_{1}$ can be decomposed into
$m+3r-3$ paths as follows:

Let
$\mathcal{P}_{24}=\\{(u_{1},y_{j})(u_{3},y_{j}),(u_{2},y_{j})(u_{4},y_{j})\\}$
for each $j\in\\{2,3,\cdots,r\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{3},y_{1})(u_{4},y_{1})\\}\\}\cup\\{(u_{1},y_{1})(u_{3},y_{1})(u_{4},y_{1}),\\\
(u_{1},y_{1})(u_{2},y_{1})(u_{4},y_{1})\\}\cup\\{\mathcal{P}_{23}\setminus\\{(u_{2},y_{r+1})(u_{3},y_{r+1})\\}\\}\cup\\{(u_{1},y_{r+1})(u_{3},y_{r+1})(u_{2},y_{r+1})(u_{4},y_{r+1})\\}\\\
\cup\mathcal{P}_{24}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(m+3r_{i}-3)\leq\sum_{i=1}^{t_{2}}\frac{m(r_{i}+1)}{2}\leq\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

Case 2. If $m=5$, then $P_{m}\boxdot W_{1}$ can be decomposed into at most
$\frac{5r+3}{2}$ paths as follows:

When $r$ is even,
$\mathcal{P}_{24}=\\{(u_{4},y_{1})(u_{3},y_{1})(u_{1},y_{1})P^{1}_{y_{1},y_{2}}(u_{1},y_{2})(u_{3},y_{2})\\}\cup\\{\\{(u_{3},y_{j})(u_{1},y_{j})\\\
P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}$ for each
$j\in\\{3,5,\cdots,r-1\\}$}.

When $r$ is odd,
$\mathcal{P}_{24}=\\{(u_{4},y_{1})(u_{3},y_{1})(u_{1},y_{1})P^{1}_{y_{1},y_{2}}(u_{1},y_{2})(u_{3},y_{2})\\}\cup\\{(u_{1},y_{r})(u_{3},y_{r})\\}\cup\\{\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}$
for each $j\in\\{3,5,\cdots,r-2\\}$}.

$\mathcal{P}_{25}=\\{(u_{1},y_{1})(u_{2},y_{1})(u_{4},y_{1})\\}\cup\\{\\{(u_{2},y_{j})(u_{4},y_{j})\\}$
for each $j\in\\{2,3,\cdots,r\\}$}.

Let $\mathcal{P^{\prime}}_{21}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{21}\ and\ Q\in\mathcal{P}_{24}\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P^{\prime}}_{21}\cup\mathcal{P}_{24}\cup\mathcal{P}_{25}\cup\\{(u_{1},y_{r+1})(u_{3},y_{r+1})(u_{2},y_{r+1})(u_{4},y_{r+1})(u_{5},y_{r+1})\\}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}\frac{5r_{i}+3}{2}\leq\sum_{i=1}^{t_{2}}\frac{5(r_{i}+1)}{2}=\frac{5}{2}(n_{o}^{2}(H)+n_{e}^{1}(H))$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

Case 3. If $m=4$, then $P_{m}\boxdot W_{1}$ can be decomposed into at most
$2r+1$ paths as follows:

When $r$ is odd,
$\mathcal{P}_{24}=\\{(u_{4},y_{1})(u_{3},y_{1})P^{1}_{y_{1},y_{2}}(u_{1},y_{1})(u_{1},y_{2})(u_{3},y_{2})\\}\cup\\{(u_{1},y_{1})(u_{2},y_{1})\\\
(u_{4},y_{1})P^{4}_{y_{1},y_{2}}(u_{4},y_{2})(u_{2},y_{2})\\}\cup\\{(u_{1},y_{r+1})(u_{3},y_{r+1})(u_{2},y_{r+1})(u_{4},y_{r+1})\\}$,

$\mathcal{P}_{25}=\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}\cup\\{(u_{2},y_{j})(u_{4},y_{j})P^{4}_{y_{j},y_{j+1}}(u_{4},y_{j+1})\\\
(u_{2},y_{j+1})\\}$ for each $j\in\\{3,4,\cdots,r-1\\}$.

When $r$ is even,
$\mathcal{P}_{24}=\\{(u_{4},y_{1})(u_{3},y_{1})(u_{1},y_{1})P^{1}_{y_{1},y_{2}}(u_{1},y_{2})(u_{3},y_{2})\\}\cup\\{(u_{1},y_{1})(u_{2},y_{1})\\\
(u_{4},y_{1})P^{4}_{y_{1},y_{2}}(u_{4},y_{2})(u_{2},y_{2})\\}\cup\\{(u_{3},y_{r})(u_{1},y_{r})P^{1}_{y_{r},y_{r+1}}(u_{1},y_{r+1})(u_{3},y_{r+1})(u_{2},y_{r+1})(u_{4},y_{r+1})\\\
P^{4}_{y_{r},y_{r+1}}(u_{4},y_{r})(u_{2},y_{r})\\}$,

$\mathcal{P}_{25}=\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}\cup\\{(u_{2},y_{j})(u_{4},y_{j})P^{4}_{y_{j},y_{j+1}}(u_{4},y_{j+1})\\\
(u_{2},y_{j+1})\\}$ for each $j\in\\{3,4,\cdots,r-2\\}$.

Let $\mathcal{P^{\prime}}_{21}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{21}\ and\
Q\in\\{\mathcal{P}_{24},\mathcal{P}_{25}\\}\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P^{\prime}}_{21}\cup\mathcal{P}_{24}\cup\mathcal{P}_{25}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(2r_{i}+1)\leq\sum_{i=1}^{t_{2}}2(r_{i}+1)=2(n_{o}^{2}(H)+n_{e}^{1}(H))$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

(3) For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, we will consider the three
cases as follows:

Case 1. If $m\geq 6$, then $P_{m}\boxdot W_{2}$ can be decomposed into $3r$
paths as follows:

Let
$\mathcal{P}_{32}=\\{(u_{1},y_{j})(u_{3},y_{j}),(u_{2},y_{j})(u_{4},y_{j})\\}$
for each $j\in\\{1,3,\cdots,r\\}$,

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}3r_{i}\leq\frac{mn_{e}^{2}(H)}{2}$ where
$r_{i}$ is the number of paths on $W_{2_{i}}$.

Case 2. If $m=5$, then $P_{m}\boxdot W_{2}$ can be decomposed into at most
$\frac{5r}{2}$ paths as follows:

When $r$ is even,
$\mathcal{P}_{32}=\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}$
for each $j\in\\{1,3,\cdots,\\\ r-1\\}$.

$\mathcal{P}_{33}=\\{(u_{2},y_{j})(u_{4},y_{j})\\}$ for each
$j\in\\{1,2,\cdots,r\\}$.

Let $\mathcal{P^{\prime}}_{31}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{31}\ and\ Q\in\mathcal{P}_{32}\\}$.

$\mathcal{P}(G\boxdot
W_{2})=\mathcal{P^{\prime}}_{31}\cup\mathcal{P}_{32}\cup\mathcal{P}_{33}.$

When $r$ is odd,
$\mathcal{P}_{32}=\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}$
for each $j\in\\{2,4,\cdots,\\\ r-1\\}$,

$\mathcal{P}_{33}=\\{(u_{2},y_{j})(u_{4},y_{j})\\}$ for each
$j\in\\{1,2,\cdots,r\\}$.

Let
$\mathcal{P^{\prime}}_{31}=\\{\\{\bigcup_{i=2}^{5}P_{y_{r-1},y_{r}}^{i}\\}\cup\\{P_{y_{r},y_{1}}^{1}\\}\cup\\{(u_{1},y_{r})(u_{2},y_{r}),(u_{2},y_{r-1})(u_{3},y_{r-1}),(u_{3},y_{r})(u_{4},y_{r}),\\\
(u_{4},y_{r-1})(u_{5},y_{r-1})\\}\cup\\{(u_{1},y_{1})(u_{3},y_{1})\\}\\}\cup\\{\\{\bigcup_{i=2}^{5}P_{y_{r},y_{1}}^{i}\\}\cup\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{2},y_{r})(u_{3},y_{r}),\\\
(u_{3},y_{1})(u_{4},y_{2}),(u_{4},y_{r})(u_{5},y_{r})\\}\\}\cup\\{\\{\bigcup_{i=1}^{5}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{1},y_{j+1})(u_{2},y_{j+1}),(u_{2},y_{j})(u_{3},y_{j}),\\\
(u_{3},y_{j+1})(u_{4},y_{j+1}),(u_{4},y_{j})(u_{5},y_{j})\\}$ for each
$j\in\\{1,\cdots,r-2\\}$},

$\mathcal{P^{\prime\prime}}_{31}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P^{\prime}}_{31}\ and\ Q\in\mathcal{P}_{32}\\}$.

$\mathcal{P}(G\boxdot
W_{2})=\mathcal{P^{\prime\prime}}_{31}\cup\mathcal{P}_{32}\cup\mathcal{P}_{33}.$

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}\frac{5r_{i}}{2}=\frac{5n_{e}^{2}(H)}{2}$
where $r_{i}$ is the number of paths on $W_{2_{i}}$.

Case 3. If $m=4$, then $P_{m}\boxdot W_{2}$ can be decomposed into $2r$ paths
as follows:

When $r$ is even,
$\mathcal{P}_{32}=\\{(u_{3},y_{j})(u_{1},y_{j})P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}\cup\\{(u_{2},y_{j})(u_{4},y_{j})\\\
P^{4}_{y_{j},y_{j+1}}(u_{4},y_{j+1})(u_{2},y_{j+1})\\}$ for each
$j\in\\{1,3,\cdots,r-1\\}$.

Let $\mathcal{P^{\prime}}_{31}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P}_{31}\ and\ Q\in\mathcal{P}_{32}\\}$.

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P^{\prime}}_{31}\cup\mathcal{P}_{32}$.

When $r$ is odd,
$\mathcal{P}_{32}=\\{(u_{2},y_{j})(u_{4},y_{j})P^{4}_{y_{j},y_{j+1}}(u_{4},y_{j+1})(u_{2},y_{j+1})\\}\cup\\{(u_{3},y_{j})(u_{1},y_{j})\\\
P^{1}_{y_{j},y_{j+1}}(u_{1},y_{j+1})(u_{3},y_{j+1})\\}$ for each
$j\in\\{2,4,\cdots,r-1\\}$.

Let
$\mathcal{P^{\prime}}_{31}=\\{\\{\bigcup_{i=2}^{3}P_{y_{r-1},y_{r}}^{i}\\}\cup\\{P_{y_{r},y_{1}}^{1}\\}\cup\\{P_{y_{r},y_{1}}^{4}\\}\cup\\{(u_{1},y_{r})(u_{2},y_{r}),(u_{2},y_{r-1})(u_{3},y_{r-1}),\\\
(u_{3},y_{r})(u_{4},y_{r})\\}\cup\\{(u_{1},y_{1})(u_{3},y_{1}),(u_{2},y_{1})(u_{4},y_{1})\\}\\}\cup\\{\\{\bigcup_{i=2}^{3}P_{y_{r},y_{1}}^{i}\\}\cup\\{(u_{1},y_{1})(u_{2},y_{1}),\\\
(u_{2},y_{r})(u_{3},y_{r}),(u_{3},y_{1})(u_{4},y_{2})\\}\\}\cup\\{\\{\bigcup_{i=1}^{4}P_{y_{j},y_{j+1}}^{i}\\}\cup\\{(u_{1},y_{j+1})(u_{2},y_{j+1}),(u_{2},y_{j})(u_{3},y_{j}),\\\
(u_{3},y_{j+1})(u_{4},y_{j+1})\\}$ for each $j\in\\{1,\cdots,r-2\\}$},

$\mathcal{P^{\prime\prime}}_{31}=\\{P^{\prime}:P^{\prime}=P-\\{P\cap
Q\\},P\in\mathcal{P^{\prime}}_{31}\ and\ Q\in\mathcal{P}_{32}\\}$.

$\mathcal{P}(G\boxdot
W_{2})=\mathcal{P^{\prime\prime}}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}2r_{i}\leq 2n_{e}^{2}(H)$ where $r_{i}$ is the
number of paths on $W_{2_{i}}$.

The above evidence shows that $G\Box H$ has a path decomposition
$\mathcal{P}(G\Box H)$ with

$\displaystyle p(G\Box H)$ $\displaystyle\leq$ $\displaystyle p(G\boxdot
H_{1})+p(G\boxdot H_{2})+p(G\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{mn_{o}^{1}(H)}{2}+\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{mn_{e}^{2}(H)}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

######  Lemma 3.4.

Let $G$ be a connected graph of order $m$ and $H$ be a connected graph of
order $n$. If $G\in\mathcal{G}$, then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $G=P_{m}+\\{u_{1}u_{3},u_{m-2}u_{m}\\}$ where $P_{m}=u_{1}u_{2}\cdots
u_{m}$, $m\geq 6$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $G\boxdot
P_{y_{1},y_{2}}$ can be decomposed into $m$ paths as follows:

If $m$ is even, then

$\mathcal{P^{\prime}}_{12}=\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{m-1},y_{1})(u_{m},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),(u_{m-2},y_{1})\\\
(u_{m},y_{1})(u_{m-1},y_{1})\\}$.

$\mathcal{P^{\prime}}_{13}=\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{2})(u_{3},y_{2}),(u_{m-2},y_{2})(u_{m-1},y_{2})\\}\\}\cup\\{(u_{1},y_{2})(u_{3},y_{2})(u_{2},y_{2}),(u_{m-1},y_{2})\\\
(u_{m-2},y_{2})(u_{m},y_{2})\\}$.

If $m$ is odd, then

$\mathcal{P^{\prime}}_{12}=\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{m-2},y_{1})(u_{m_{1}},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),(u_{m-1},y_{1})\\\
(u_{m-2},y_{1})(u_{m},y_{1})\\}$.

$\mathcal{P^{\prime}}_{13}=\\{\mathcal{P}_{13}\setminus\\{(u_{2},y_{2})(u_{3},y_{2}),(u_{m-1},y_{2})(u_{m},y_{2})\\}\\}\cup\\{(u_{1},y_{2})(u_{3},y_{2})(u_{2},y_{2}),(u_{m-1},y_{2})\\\
(u_{m},y_{2})(u_{m-2},y_{2})\\}$

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\mathcal{P^{\prime}}_{12}\cup\mathcal{P^{\prime}}_{13}$.

Then $p(G\boxdot H_{1})\leq\sum_{i=1}^{t_{1}}p(G\boxdot
P_{y_{1_{i}},y_{2_{i}}})=\sum_{i=1}^{t_{1}}p(G\Box
P_{2})\leq\frac{mn_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, $G\boxdot W_{1}$ can be
decomposed into $m+2r-2$ paths as follows:

If $m$ is even, then

$\mathcal{P^{\prime}}_{22}=\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{m-1},y_{1})(u_{m},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),(u_{m-2},y_{1})\\\
(u_{m},y_{1})(u_{m-1},y_{1})\\}$.

$\mathcal{P^{\prime}}_{23}=\\{\mathcal{P}_{23}\setminus\\{(u_{2},y_{r+1})(u_{3},y_{r+1}),(u_{m-2},y_{r+1})(u_{m-1},y_{r+1})\\}\\}\cup\\{(u_{1},y_{r+1})(u_{3},y_{r+1})\\\
(u_{2},y_{r+1}),(u_{m-1},y_{r+1})(u_{m-2},y_{r+1})(u_{m},y_{r+1})\\}$.

If $m$ is odd, then

$\mathcal{P^{\prime}}_{22}=\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{m-2},y_{1})(u_{m_{1}},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{3},y_{1}),(u_{m-1},y_{1})\\\
(u_{m-2},y_{1})(u_{m},y_{1})\\}$.

$\mathcal{P^{\prime}}_{23}=\\{\mathcal{P}_{23}\setminus\\{(u_{2},y_{r+1})(u_{3},y{r+1}),(u_{m-1},y_{r+1})(u_{m},y_{r+1})\\}\\}\cup\\{(u_{1},y_{r+1})(u_{3},y_{r+1})\\\
(u_{2},y_{r+1}),(u_{m-1},y_{r+1})(u_{m},y_{r+1})(u_{m-2},y_{r+1})\\}$

$\mathcal{P}_{24}=\\{(u_{1},y_{j})(u_{3},y_{j})(u_{5},y_{j})\\}$ for each
$j\in\\{2,3,\cdots,r\\}$.

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\mathcal{P^{\prime}}_{22}\cup\\{\mathcal{P^{\prime}}_{13}\cup\mathcal{P}_{24}$.

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(m+2r_{i}-2)\leq\sum_{i=1}^{t_{2}}\frac{m(r_{i}+1)}{2}\leq\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

(3) For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, $G\boxdot W_{2}$ can be
decomposed into $2r$ paths as follows:

$\mathcal{P}_{32}=\\{(u_{1},y_{j})(u_{3},y_{j}),(u_{m-2},y_{j})(u_{m},y_{j})\\}$
for each $j\in\\{1,2,\cdots,r\\}$.

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}2r_{i}\leq\frac{mn_{e}^{2}(H)}{2}$ where
$r_{i}$ is the number of paths on $W_{2_{i}}$.

All in all, we conclude that $G\Box H$ has a path decomposition
$\mathcal{P}(G\Box H)$ with

$\displaystyle p(G\Box H)$ $\displaystyle\leq$ $\displaystyle p(G\boxdot
H_{1})+p(G\boxdot H_{2})+p(G\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{mn_{o}^{1}(H)}{2}+\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{mn_{e}^{2}(H)}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

##  4 Cartesian product of two general graph

Let $\mathcal{W}$ be the family of all graphs, which are obtained from a cycle
and a path by identifying a vertex of the cycle with an end vertex of a
separate path $P$.

######  Lemma 4.1.

Let $G$ be a connected graph of order $m$ and $H$ be a connected graph of
order $n$. If $G\in\mathcal{W}$, then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $G=P_{m}+u_{1}u_{l}$ where $P_{m}=u_{1}u_{2}\cdots u_{m}$. If $m\geq 4$
and $m\geq l\geq 3$, by a similar argument as in above, we can fined a path
decomposition of $G\Box H$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, we will
consider the following two cases.

If $l$ is even, then $G\boxdot P_{y_{1},y_{2}}$ can be decomposed into $m$
paths as follows:

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\\{\mathcal{P}_{12}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{l-1},y_{1})(u_{l},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{l},y_{1})\\\
(u_{l-1},y_{1})\\}\cup\mathcal{P}_{13}\cup(u_{1},y_{2})(u_{l},y_{2})$.

If $l$ is odd, then $G\boxdot P_{y_{1},y_{2}}$ can be decomposed into $m$
paths as follows:

$\mathcal{P}(G\boxdot
P_{y_{1},y_{2}})=\mathcal{P}_{11}\cup\\{\mathcal{P}_{12}\setminus(u_{1},y_{1})(u_{2},y_{1})\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{l},y_{1})\\}\cup\\{\mathcal{P}_{13}\setminus(u_{l-1},y_{2})(u_{l},y_{2})\\}\cup\\{(u_{1},y_{2})(u_{l},y_{2})(u_{l-1},y_{2})\\}$

Then $p(G\boxdot H_{1})\leq\sum_{i=1}^{t_{1}}p(G\boxdot
P_{y_{1_{i}},y_{i_{2}}})=\sum_{i=1}^{t_{1}}p(G\Box
P_{2})\leq\frac{mn_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, we will consider the
following two cases.

Let $\mathcal{P}_{24}=\\{(u_{1},y_{j})(u_{l},y_{j})\\}$ for each
$j\in\\{2,3,\cdots,r\\}$,

If $l$ is even, then $G\boxdot W_{1}$ can be decomposed into $m+2r-2$ paths as
follows:

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\\{\mathcal{P}_{22}\setminus\\{(u_{1},y_{1})(u_{2},y_{1}),(u_{l-1},y_{1})(u_{l},y_{1})\\}\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{l},y_{1})\\\
(u_{l-1},y_{1})\\}\cup\mathcal{P}_{23}\cup(u_{1},y_{r+1})(u_{l},y_{r+1})\cup\mathcal{P}_{24}$

If $l$ is odd, then $G\boxdot W_{1}$ can be decomposed into $m+2r-2$ paths as
follows:

$\mathcal{P}(G\boxdot
W_{1})=\mathcal{P}_{21}\cup\\{\mathcal{P}_{22}\setminus(u_{1},y_{1})(u_{2},y_{1})\\}\cup\\{(u_{2},y_{1})(u_{1},y_{1})(u_{l},y_{1})\\}\cup\\{\mathcal{P}_{23}\setminus(u_{l-1},y_{r+1})\\\
(u_{l},y_{r+1})\\}\cup\\{(u_{1},y_{r+1})(u_{l},y_{r+1})(u_{l-1},y_{r+1})\\}\cup\mathcal{P}_{24}$

Then $p(G\boxdot H_{2})\leq\sum_{i=1}^{t_{2}}p(G\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(m+2r_{i}-2)\leq\sum_{i=1}^{t_{2}}\frac{m(r_{i}+1)}{2}\leq\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$
where $r_{i}$ is the number of paths on $W_{1_{i}}$.

(3) For a $\mathcal{P}$-$r$-closed-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, $G\boxdot W_{2}$ can be
decomposed into $2r$ paths as follows:

Let $\mathcal{P}_{32}=\\{(u_{1},y_{j})(u_{l},y_{j})\\}$ for each
$j\in\\{1,3,\cdots,r\\}$,

$\mathcal{P}(G\boxdot W_{2})=\mathcal{P}_{31}\cup\mathcal{P}_{32}$.

Then $p(G\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(G\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}2r_{i}\leq\sum_{i=1}^{t_{3}}\frac{m(r_{i}+1)}{2}\leq\frac{mn_{e}^{2}(H)}{2}$
where $r_{i}$ is the number of paths on $W_{2_{i}}$.

For these reasons, we conclude that $G\Box H$ has a path decomposition
$\mathcal{P}(G\Box H)$ with

$\displaystyle p(G\Box H)$ $\displaystyle\leq$ $\displaystyle p(G\boxdot
H_{1})+p(G\boxdot H_{2})+p(G\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{mn_{o}^{1}(H)}{2}+\frac{m(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{mn_{e}^{2}(H)}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

Now we consider the case of $l=m=3$.

(1) For an odd-odd path $P_{y_{1},y_{2}}$ of $\mathcal{P}(H)$, $G\boxdot
P_{y_{1},y_{2}}$ can be decomposed into three paths as follows:

$(u_{1},y_{1})(u_{2},y_{1})(u_{3},y_{1})\cup
P_{y_{1},y_{2}}^{3}\cup(u_{3},y_{2})(u_{2},y_{2})(u_{1},y_{2})$,
$(u_{3},y_{1})(u_{1},y_{1})\cup P_{y_{1},y_{2}}^{1}\cup(u_{1},y_{2})\\\
(u_{3},y_{2})$ and $P_{y_{1},y_{2}}^{2}$.

Then $p(C_{3}\boxdot H_{1})=\sum_{i=1}^{t_{1}}p(C_{3}\boxdot
P_{y_{1_{i}},y_{2_{i}}})=\frac{n_{o}^{1}(H)}{2}p(C_{3}\Box
P_{2})\leq\frac{3n_{o}^{1}(H)}{2}$.

(2) For a $\mathcal{P}$-$r$-trail $W_{1}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r},y_{r+1}}y_{r+1}$ of $\mathcal{P}(H)$, $G\boxdot W_{1}$ can be
decomposed into $r+2$ paths as follows:

$P_{y_{i},y_{i+1}}^{1}(u_{1},y_{j+1})(u_{2},y_{j+1})P_{y_{i+1},y_{i+2}}^{2}(u_{2},y_{j+2})(u_{3},y_{j+2})P_{y_{i+2},y_{i+3}}^{3}(u_{3},y_{j+3})(u_{1},y_{j+3})$
for each $j\in\\{1,2,\cdots,r\\}$,

$(u_{3},y_{1})(u_{1},y_{1})(u_{2},y_{1})P_{y_{1},y_{2}}^{2}(u_{2},y_{2})(u_{3},y_{2})P_{y_{2},y_{3}}^{3}(u_{3},y_{3})(u_{1},y_{3})$,

and $(u_{2},y_{1})(u_{3},y_{1})P_{y_{1},y_{2}}^{3}(u_{3},y_{2})(u_{1},y_{2})$.

Then $p(C_{3}\boxdot H_{2})=\sum_{i=1}^{t_{2}}p(C_{3}\boxdot
W_{1_{i}})\leq\sum_{i=1}^{t_{2}}(r_{i}+2)\leq\sum_{i=1}^{t_{2}}\frac{3(r_{i}+1)}{2}=\frac{3(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}$.

(3) For a $\mathcal{P}$-$r$-trail $W_{2}=y_{1}P_{y_{1},y_{2}}\cdots
y_{r}P_{y_{r}y_{1}}y_{1}$ of $\mathcal{P}(H)$, $G\boxdot W_{2}$ can be
decomposed into $r$ paths as follows:

$P_{y_{j},y_{j+1}}^{1}(u_{1},y_{j+1})(u_{2},y_{j+1})P_{y_{j+1},y_{j+2}}^{2}(u_{2},y_{j+2})(u_{3},y_{j+2})P_{y_{j+2},y_{j+3}}^{3}(u_{3},y_{j+3})(u_{1},y_{j+3})$
for each $j\in\\{1,2,\cdots,r\\}$, where the subscripts are taken modular $r$.

Then $p(C_{3}\boxdot H_{3})\leq\sum_{i=1}^{t_{3}}p(C_{3}\boxdot
W_{2_{i}})\leq\sum_{i=1}^{t_{3}}r_{i}\leq\frac{3n_{e}^{2}(H)}{2}$.

Similarly, $G\Box H$ has a path decomposition $\mathcal{P}(G\Box H)$ with

$\displaystyle p(G\Box H)$ $\displaystyle=$ $\displaystyle p(C_{3}\boxdot
H_{1})+p(C_{3}\boxdot H_{2})+p(C_{3}\boxdot H_{3})$ $\displaystyle\leq$
$\displaystyle\frac{3n_{o}^{1}(H)}{2}+\frac{3(n_{o}^{2}(H)+n_{e}^{1}(H))}{2}+\frac{3n_{e}^{2}}{2}$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

######  Corollary 4.2.

Let $m$ be an integer $m\geq 3$ and $H$ be a connected graph of order $n$. If
$G=C_{m}\Box H$, then $p(G)\leq\frac{mn}{2}$.

Let $\mathcal{F}(G)$ be a family of edge-disjoint virtual-real path and
virtual-real cycle of $G$ with
$E(G)=\\{\cup_{P\in\mathcal{F}(G)}E(P)\\}\cup\\{\cup_{C\in\mathcal{F}(G)}E(C)\\}$.
Let $v$ be any vertex in $G$. It is assigned to be real on the path in
$\mathcal{F}(G)$ with $v$ as an end vertex if $v$ is odd, and is assigned to
virtual for the remaining paths and cycles containing it; If $v$ is even, it
is assigned to be real on unique a (randomly chosen) path or cycle in
$\mathcal{F}(G)$ containing $v$, and is assigned to virtual for the remaining
paths and cycles containing it. We say $\mathcal{F}(G)$ is a virtual-real path
cycle decomposition of $G$. Specifically, if there are no virtual-real cycles
in $\mathcal{F}(G)$, then $\mathcal{F}(G)$ is called a virtual-real path
decomposition.

######  Theorem 4.3.

Let $G$ be a connected graph of order $m\geq 2$ and $H$ be a connected graph
of order $n$. If $G$ has a virtual-real path cycle decomposition, then
$p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

We assume that graph $G$ can be decomposed into $t_{1}$ virtual-real paths and
$t_{2}$ virtual-real cycles. Let $\mathcal{F}(G)=\\{P_{l_{i}}^{s_{i}}:1\leq
i\leq t_{1}\\}\cup\\{C_{l_{j}}^{s_{j}}:1\leq j\leq t_{2}\\}$ where
$P_{l_{i}}^{s_{i}}$ is a virtual-real path with $l_{i}$ vertices and $s_{i}$
real vertices and $C_{l_{j}}^{s_{j}}$ is a virtual-real cycle with $l_{j}$
vertices and $s_{j}$ real vertices. Based on the above facts, it follows that
$\sum_{i=1}^{t_{1}}s_{i}+\sum_{j=1}^{t_{2}}s_{i}=m$. It is obvious that
$E(G\Box H)=\\{\cup_{i=1}^{t_{1}}E(P_{l_{i}}^{s_{i}}\boxdot
H)\\}\cup\\{\cup_{j=1}^{t_{2}}E(C_{l_{j}}^{s_{j}}\boxdot H)\\}$. By Lemma 2.2,
$p(P_{l_{i}}^{s_{i}}\boxdot H)=p(P_{s_{i}}\Box H)$ and
$p(C_{l_{i}}^{s_{i}}\boxdot H)=p(C_{s_{i}}\Box H)$. Moreover, by Theorem 1.2
and Corollary 4.2,

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t_{1}}p(P_{l_{i}}^{s_{i}}\boxdot
H)+\sum_{j=1}^{t_{2}}p(C_{l_{j}}^{s_{j}}\boxdot H)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{t_{1}}p(P_{s_{i}}\Box
H)+\sum_{j=1}^{t_{2}}p(C_{s_{j}}\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t_{1}}\frac{ns_{i}}{2}+\sum_{j=1}^{t_{2}}\frac{ns_{j}}{2}$
$\displaystyle=$
$\displaystyle\frac{n}{2}(\sum_{i=1}^{t_{1}}s_{i}+\sum_{j=1}^{t_{2}}s_{j})$
$\displaystyle=$ $\displaystyle\frac{mn}{2}.$

∎

##  5 Cartesian product of a graph and a unicyclic graph

Let $C:=u_{1}u_{2}u_{3}\cdots u_{l}u_{1}$ be a cycle. For any $1\leq i<j\leq
l$, we denote by $C_{u_{i},u_{j}}$ the path $u_{i}u_{i+1}\cdots u_{j}$ in $C$,
and by $C_{u_{j},u_{i}}$ the path $u_{j}u_{j+1}\cdots u_{1}\cdots u_{i}$ in
$C$. The following lemma is what we are going to use.

######  Theorem 5.1 ([10]).

For any tree $T$, $p(T)=\frac{n_{o}(T)}{2}$.

Now we are ready to prove one of our main results.

######  Theorem 5.2.

Let $G$ be a unicyclic graph of order $m\geq 3$ and $H$ be a connected graph
of order $n$. Then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Let $C:=u_{1}u_{2}u_{3}\cdots u_{l}u_{1}$, $3\leq l\leq m$ be the cycle of
$G$. By Corollary 4.2, the result holds if $l=m$. So, let $m\leq l$. Let
$G^{\prime}=G-E(C)$. It is clearly that $G^{\prime}$ is a forest. By Theorem
5.1, there exists a path decomposition $\mathcal{P}(G^{\prime})$, such that
each odd vertex is the end vertex of exactly one path of
$\mathcal{P}(G^{\prime})$ and each even vertex is not end vertex. Therefore,
$G^{\prime}$ has a virtual-real path decomposition $\mathcal{F}(G^{\prime})$,
and for any vertex $u_{i}\in V(G^{\prime})$, there exists a virtual-real path
$P^{i}$ of $\mathcal{F}(G^{\prime})$ such that $u_{i}$ is real on $P^{i}$.

Let $S=\\{u_{i}:u_{i}\in V(C)\ and\ d_{G}(u_{i})>2\\}$ and
$\mathcal{L}=\\{P^{i}:u_{i}\in S\\}$. Let $P^{\prime i}$ be the path obtained
from $P^{i}$ by changing $u_{i}$ from real vertex to virtual vertex. Let
$\mathcal{L^{\prime}}=\\{P^{\prime i}:P^{i}\in\mathcal{L}\\}$. If all vertices
on $C$ are even in $G$, then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})-\mathcal{L}\\}\cup\mathcal{L^{\prime}}$
and $C$. By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$. Now let’s assume that
there is at least one odd vertex on $C$.

Case 1. At least two odd vertices in $C$.

Suppose that $u_{1}$ and $u_{2}$ of $V(C)$ are odd vertices in $G$. Then
$u_{1}$ and $u_{2}$ are the end vertices of $P^{1}$ and $P^{2}$, respectively.
Moreover, we can fined a virtual-real path decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{1},P^{2}\\}\\}\cup\\{P^{1}\cup
C_{u_{1},u_{2}},P^{2}\cup C_{u_{2},u_{1}}\\}$ of $G$ with
$p(G)=p(G^{\prime})=\frac{n_{o}(G)}{2}$. By Theorem 1.3, $p(G\Box
H)\leq\frac{mn}{2}$.

Case 2. Only one odd vertex in $C$.

Suppose that $u_{1}\in V(C)$ is an odd vertex in $G$. Then $G$ can be
decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{1}\\}\\}\cup\mathcal{L^{\prime}}$ and $C^{\prime}=C\cup P^{1}$. Suppose the
number of real vertices of $C^{\prime}$ is $s$. By Lemma 4.1 and Theorem 1.3,
we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(C^{\prime}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s)}{2}+\frac{ns}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

The proof is now finish. ∎

##  6 Cartesian product of a graph and a bicyclic graph

In this section, we discuss the path decomposition of the cartesian product of
a graph and a bicyclic graph. To simplify our statement, we give the following
general definitions.

To split a vertex $v$ is to replace $v$ by two nonadjacent vertices,
$v^{\prime}$ and $v^{\prime\prime}$, and to replace each edge incident to $v$
by an edge incident to either $v^{\prime}$ or $v^{\prime\prime}$ (but not
both, unless it is a loop at $v$), the other end of the edge remaining
unchanged.

######  Theorem 6.1.

Let $G$ be a bicyclic graph of order $m$ and $H$ be a connected graph of order
$n$. Then $p(G\Box H)\leq\frac{mn}{2}$.

###### Proof.

Suppose $C_{l_{1}}:=u_{1}u_{2}u_{3}\cdots u_{l_{1}}u_{1}$ and
$C_{l_{2}}:=v_{1}v_{2}v_{3}\cdots v_{l_{2}}v_{1}$ are the cycles of graph $G$.
Let $U=V(C_{l_{1}})\cup V(C_{l_{2}})$ and $D=G[U]$. If $G^{\prime}=G-E(D)$,
then $G^{\prime}$ is a forest. By Theorem 5.1, there exists a path
decomposition $\mathcal{P}(G^{\prime})$, such that each odd vertex is the end
vertex of exactly one path of $\mathcal{P}(G^{\prime})$ and each even vertex
is not end vertex. Therefore, $G^{\prime}$ has a virtual-real path
decomposition $\mathcal{F}(G^{\prime})$, and for any vertex $u_{i}\in
V(C_{l_{1}})$, there exists a virtual-real path $P^{i}$ of
$\mathcal{F}(G^{\prime})$ such that $u_{i}$ is real on $P^{i}$, for any vertex
$v_{j}\in V(C_{l_{2}})$, there exists a virtual-real path $Q^{j}$ of
$\mathcal{F}(G^{\prime})$ such that $v_{j}$ is real on $Q^{j}$. Let $P^{\prime
i}$ be the path obtained from $P^{i}$ by changing $x_{i}$ from real vertex to
virtual vertex where $x_{i}\in U$. Now we consider the path decomposition of
edge of $D$.

(1) $|N(C_{l_{1}})\cap N(C_{l_{2}})|=0$.

Let $U^{\prime}=U-\\{u_{1},v_{1}\\}$. Let $S=\\{x_{i}:x_{i}\in U^{\prime}\
and\ d_{G^{\prime}}(x_{i})\ is\ even\ and\ at\ least\ two\\}$,
$\mathcal{L}=\\{P^{i}:x_{i}\in S\\}$ and $\mathcal{L^{\prime}}=\\{P^{\prime
i}:P^{i}\in\mathcal{L}\\}$. Assuming $P_{u_{1},v_{1}}$ is the path connecting
$u_{1}$ and $v_{1}$ in $G$. Now we consider the following subcases.

Case 1. There exists an odd vertex in $C_{l_{1}}-u_{1}$.

Without loss of generality, suppose $u_{2}$ is the odd vertex in
$C_{l_{1}}-u_{1}$. We consider the following subcases.

Subcase 1.1. There exists an odd vertex in $C_{l_{2}}-v_{1}$, say $v_{2}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are even, then must exists a path
$P_{x,y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$, where
$u_{1}$ and $v_{1}$ are virtual. Then we can obtain a virtual-real path
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{2},Q^{2},P_{x,y}\\}\\}\cup\\{P^{2}\cup
C_{u_{2},u_{1}}\cup P_{u_{1},v_{1}}\cup C_{v_{1},v_{2}}\cup
Q^{2}\\}\cup\\{P_{x,u_{1}}\cup C_{u_{1},u_{2}}\\}\cup\\{P_{y,v_{1}}\cup
C_{v_{2},v_{1}}\\}$. By Theorem 1.3, $p(G\Box H)\leq\frac{mn}{2}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are odd, then $P_{u_{1},v_{1}}$ ia a
path in $\mathcal{F}(G^{\prime})$. Thus, we can obtain a virtual-real path
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{2},Q^{2},P_{u_{1},v_{1}}\\}\\}\cup\\{P^{2}\cup
C_{u_{1},u_{2}}\\}\cup\\{C_{u_{2},u_{1}}\cup P_{u_{1},v_{1}}\cup
C_{v_{2},v_{1}}\\}\cup\\{C_{v_{1},v_{2}}\cup Q^{2}\\}$. By Theorem 1.3,
$p(G\Box H)\leq\frac{mn}{2}$.

Now we consider the case of $d_{G}(u_{1})$ and $d_{G}(v_{1})$ have different
parity. Suppose that $d_{G}(u_{1})$ is even and $d_{G}(v_{1})$ is odd, then
exists a path $P_{x,v_{1}}$ in $\mathcal{F}(G^{\prime})$ that contains
$P_{u_{1},v_{1}}$, where $u_{1}$ is virtual and $v_{2}$ is real. Then we can
obtain two virtual-real paths $P_{x,v_{1}}\cup C_{v_{1},v_{2}}$ and $Q^{2}\cup
C_{v_{2}v_{1}}$. Now we consider the path decomposition of $C_{l_{1}}$.

If there exists an odd vertex in $C_{l_{1}}-\\{u_{1},u_{2}\\}$, say $u_{3}$,
then $P^{2}\cup C_{l_{1}}\cup P^{3}$ can be decomposed into virtual-real paths
$P^{2}\cup C_{u_{2},u_{3}}$ and $P^{3}\cup C_{u_{3},u_{2}}$. By Theorem 1.3,
$p(G\Box H)\leq\frac{mn}{2}$. If there is no odd vertex in $C_{l_{1}}-u_{1}$,
then $P^{2}\cup C_{l_{1}}$ is an element of $\mathcal{W}$. Thus, $G$ can be
decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},Q^{2},P_{x,v_{1}}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P_{x,v_{1}}\cup
C_{v_{1},v_{2}}\\}\cup\\{Q^{2}\cup C_{v_{2}v_{1}}\\}$ and
$C^{\prime}_{l_{1}}=P^{2}\cup C_{l_{1}}$. Suppose the number of real vertices
of $C^{\prime}_{l_{1}}$ is $s_{1}$. By Lemma 4.1 and Theorem 1.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{1}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{1})}{2}+\frac{ns_{1}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

Next let’s assume that no odd vertex in $C_{l_{2}}-v_{1}$ and consider the
following two cases.

Subcase 1.2. There exists an odd vertex in $V(C_{l_{1}})-\\{u_{1},u_{2}\\}$,
say $u_{3}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are even, then must exists a path
$P_{x,y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$, where
$u_{1}$ and $v_{1}$ are virtual. Thus, we can obtain a virtual-real path cycle
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P^{3}\\}\\}\\}\cup\mathcal{L}\cup\\{P^{2}\cup
C_{u_{2},u_{3}}\\}\cup\\{P^{3}\cup C_{u_{3},u_{2}}\\}\cup C_{l_{2}}$. By
Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are odd, then $P_{u_{1},v_{1}}$ is a
path in $\mathcal{F}(G^{\prime})$. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P^{3}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{3}}\\}\cup\\{P^{3}\cup C_{u_{3},u_{2}}\\}$ and
$C^{\prime}_{l_{2}}=P_{u_{1},v_{1}}\cup C_{l_{2}}$. It is obvious that
$C^{\prime}_{l_{2}}\in\mathcal{W}$. Suppose the number of real vertices of
$C^{\prime}_{l_{2}}$ is $s_{2}$. By Lemma 4.1 and Theorem 1.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{2}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{2})}{2}+\frac{ns_{2}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

If $d_{G}(u_{1})$ is even and $d_{G}(v_{1})$ is odd, then exists a path
$P_{x,v_{1}}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$,
where $u_{1}$ is virtual and $v_{2}$ is real. Hence, $G$ can be decomposed
into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P^{3},P_{x,v_{1}}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{3}}\\}\cup\\{P^{3}\cup C_{u_{3},u_{2}}\\}$ and
$C^{\prime}_{l_{2}}=P_{x,v_{1}}\cup C_{l_{2}}$. It is obvious that
$C^{\prime}_{l_{2}}\in\mathcal{W}$. Similar to the above, we have $p(G\Box
H)\leq\frac{mn}{2}$.

If $d_{G}(u_{1})$ is odd and $d_{G}(v_{1})$ is even, then exists a path
$P_{u_{1},y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$,
where $u_{1}$ is real and $v_{2}$ is virtual. Thus, we can obtain a virtual-
real path cycle decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P^{3}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{3}}\\}\cup\\{P^{3}\cup C_{u_{3},u_{2}}\\}\cup C_{l_{2}}$. By
Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

Subcase 1.3. There exists no odd vertex in $V(C_{l_{1}})-\\{u_{1},u_{2}\\}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are even, then exists a path
$P_{x,y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$, where
$u_{1}$ and $v_{1}$ are virtual. Thus, we can obtain a virtual-real path cycle
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P_{x,y}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{1}}\cup P_{u_{1},y}\\}\cup\\{C_{u_{1},u_{2}}\cup
P_{x,u_{1}}\\}\cup C_{l_{2}}$. By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are odd, then $P_{u_{1},v_{1}}$ is a
path in $\mathcal{F}(G^{\prime})$. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{2}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup C_{u_{1},u_{2}}\\}$ and
$C^{\prime}_{l_{2}}=C_{u_{2},u_{1}}\cup P_{u_{1},v_{1}}\cup C_{l_{2}}$. It is
obvious that $C^{\prime}_{l_{2}}\in\mathcal{W}$. Suppose the number of real
vertices of $C^{\prime}_{l_{2}}$ is $s_{2}$. By Lemma 4.1 and Theorem 1.3, we
have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{2}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{2})}{2}+\frac{ns_{2}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

If $d_{G}(u_{1})$ is even and $d_{G}(v_{1})$ is odd, then exists a path
$P_{x,v_{1}}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$,
where $u_{1}$ is virtual and $v_{2}$ is real. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P_{x,v_{1}}\\}\\}\\}\cup\mathcal{L^{\prime}}$
and $C^{\prime}_{l_{1}}=P^{2}\cup C_{l_{1}}$ and
$C^{\prime}_{l_{2}}=P_{x,v_{1}}\cup C_{l_{2}}$. It is obvious that
$C^{\prime}_{l_{2}},C^{\prime}_{l_{2}}\in\mathcal{W}$. Similar to the above,
we have $p(G\Box H)\leq\frac{mn}{2}$.

If $d_{G}(u_{1})$ is odd and $d_{G}(v_{1})$ is even, then exists a path
$P_{u_{1},y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$,
where $u_{1}$ is real and $v_{2}$ is virtual. Thus, we can obtain a virtual-
real path cycle decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P_{u_{1},y}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{1}}\cup P_{u_{1},y}\\}\cup C_{u_{1},u_{2}}\cup C_{l_{2}}$. By
Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

Case 2. There exists no odd vertex in $C_{l_{1}}-u_{1}$.

If there are two odd vertices in $C_{l_{2}}-v_{1}$, then the proof is similar
to Subcase 1.2. If there is an odd vertex in $C_{l_{2}}-v_{1}$, then the proof
is similar to Subcase 1.3. We now suppose there is no odd vertex in
$C_{l_{2}}-v_{1}$ and consider the following subcases.

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are even, then exists a path
$P_{x,y}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$, where
$u_{1}$ and $v_{1}$ are virtual. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\\}\cup\mathcal{L^{\prime}}$,
$C_{l_{1}}$ and $C_{l_{2}}$. By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

If $d_{G}(u_{1})$ and $d_{G}(v_{1})$ have different parity, suppose that
$d_{G}(u_{1})$ is even and $d_{G}(v_{1})$ is odd, then exists a path
$P_{x,v_{1}}$ in $\mathcal{F}(G^{\prime})$ that contains $P_{u_{1},v_{1}}$,
where $u_{1}$ is virtual and $v_{2}$ is real. Hence, $G$ can be decomposed
into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P_{x,v_{1}}\\}\\}\cup\mathcal{L^{\prime}}\cup C_{l_{1}}$ and
$C^{\prime}_{l_{2}}=P_{x,v_{1}}\cup C_{l_{2}}$. It is obvious that
$C^{\prime}_{l_{2}}\in\mathcal{W}$. Suppose the number of real vertices of
$C^{\prime}_{l_{2}}$ is $s_{2}$. By Lemma 4.1 and Theorem 4.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{2}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{2})}{2}+\frac{ns_{2}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

If both $d_{G}(u_{1})$ and $d_{G}(v_{1})$ are odd, then $P_{u_{1},v_{1}}$ is a
path in $\mathcal{F}(G^{\prime})$. If $max\\{l_{1},l_{2}\\}\geq 4$, suppose
$l_{1}\geq 4$, then $C_{1}$ is a virtual-real cycle where $u_{1}$ is virtual.
Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P_{x,v_{1}}\\}\\}\cup\mathcal{L^{\prime}}\cup C_{l_{1}}$ and
$C^{\prime}_{l_{2}}=P_{x,v_{1}}\cup C_{l_{2}}$. Similar to the above, we have
$p(G\Box H)\leq\frac{mn}{2}$.

Now we consider the case of $l_{1}=l_{2}=3$. Let
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P_{u_{1},v_{1}}\\}\\}\cup\mathcal{L^{\prime}}$ and $D^{\prime}=C_{l_{1}}\cup
P_{u_{1},v_{1}}\cup C_{l_{2}}$. Clearly, $D^{\prime}\in\mathcal{G}$. Suppose
the number of real vertices of $D^{\prime}$ is $s$. By Lemma 3.4 and Theorem
1.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(D^{\prime}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s)}{2}+\frac{ns}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

(1) $|N(C_{l_{1}})\cap N(C_{l_{2}})|=1$

Suppose $u_{1}=v_{1}$ and $U^{\prime}=U-u_{1}$. Let $S=\\{x_{i}:x_{i}\in
U^{\prime}\ and\ d_{G^{\prime}}(x_{i})\ is\ even\ and\ at\ least\\\ two\\}$,
$\mathcal{L}=\\{P^{i}:x_{i}\in S\\}$ and $\mathcal{L^{\prime}}=\\{P^{\prime
i}:P^{i}\in\mathcal{L}\\}$. Now we consider the following cases.

Case 1. There exists an odd vertex in $V(C_{l_{1}})-u_{1}$.

Without loss of generality, suppose $u_{2}$ is the odd vertex in
$C_{l_{1}}-u_{1}$. We consider the following subcases.

Subcase 1.1. There exists an odd vertex in $C_{l_{2}}-v_{1}$, say $v_{2}$.

We can obtain a virtual-real path decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{2},Q^{2}\\}\\}\cup\\{P^{2}\cup
C_{u_{2}u_{1}}\cup C_{u_{1}v_{2}}\\}\cup\\{Q^{2}\cup C_{v_{2}v_{1}}\cup
C_{u_{1}u_{2}}\\}$ of $G$. By Theorem 1.3, $p(G\Box H)\leq\frac{mn}{2}$.

Next let’s assume that no odd vertex in $C_{l_{2}}-v_{1}$ and consider the
following two cases.

Subcase 1.2. There exists an odd vertex in $C_{l_{1}}-\\{u_{1},u_{2}\\}$, say
$u_{3}$.

Let $G^{\prime\prime}=G-E(C_{l_{2}})$. Then we can obtain a virtual-real path
decomposition
$\mathcal{F}(G^{\prime\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{2},P^{3}\\}\\}\cup\\{P^{2}\cup
C_{u_{2},u_{3}}\\}\cup\\{P^{3}\cup C_{u_{3},u_{2}}\\}$ of $G^{\prime\prime}$.
Next we focus on the decomposition of $C_{l_{2}}$.

If $d_{G^{\prime}}(v_{1})$ is even, then there are at least three even
vertices on $C_{l_{2}}$. Hence, we can obtain a virtual-real path cycle
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime\prime})\setminus\\{\mathcal{L}\cup
P^{1}\\}\\}\cup\\{\mathcal{L^{\prime}}\cup P^{\prime 1}\\}\cup C_{l_{2}}$ of
$G$. By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

If $d_{G^{\prime}}(u_{1})$ is odd, then $u_{1}$ is the end vertex of $P^{1}$.
If $l_{2}\geq 4$, similar to above, then $C_{l_{2}}$ is a virtual-real cycle
with at least three real vertices. Hence, $G\Box H$ has we desirous path
decomposition. If $l_{2}=3$, then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime\prime})=\mathcal{F}(G^{\prime\prime})\setminus\\{\mathcal{L}\cup
P^{1}\\}\cup\mathcal{L^{\prime}}$ and $C^{\prime}_{l_{2}}=C_{l_{2}}\cup
P^{1}$. It is clear that $C^{\prime}_{l_{2}}\in\mathcal{W}$. Suppose the
number of real vertex of $C^{\prime}_{l_{2}}$ is $s_{2}$. By Lemma 4.1 and
Theorem 4.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{2}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{2})}{2}+\frac{ns_{2}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

Subcase 1.3. There exists no odd vertex in $C_{l_{1}}-\\{u_{1},u_{2}\\}$.

If $l_{2}\geq 4$, similar to above, then $C_{l_{2}}$ is a cycle with at least
three real vertices. Let $G^{\prime\prime}=G^{\prime}+E(C_{l_{2}})$. Now we
consider the decomposition of $C_{l_{1}}$.

If $d_{G}(u_{1})$ is odd, then we can obtain a virtual-real path cycle
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1},P^{2}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{1}\cup
C_{u_{1},u_{2}}\\}\cup\\{P^{2}\cup C_{u_{2},u_{1}}\\}\cup C_{l_{2}}$ of $G$.
By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$. If $d_{G}(u_{1})$ is even, then
we can obtain $C^{\prime}_{l_{1}}=C_{l_{1}}\cup P^{2}$ which belong in
$\mathcal{W}$. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{2}\\}\\}\cup\mathcal{L^{\prime}}\cup C_{l_{2}}$ and $C^{\prime}_{l_{1}}$.
Suppose the number of real vertices of $C^{\prime}_{l_{1}}$ is $s_{1}$. By
Lemma 4.1 and Theorem 4.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime\prime})}p(P\boxdot
H)+p(C^{\prime}_{l_{1}}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s_{1})}{2}+\frac{ns_{1}}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

Now we consider the case of $l_{2}=3$. If $l_{1}\geq 4$, then we can obtain
$C^{\prime}_{l_{1}}=C_{l_{1}}\cup P^{2}$ where $u_{1}$ is virtual. If
$d_{G}(u_{1})$ is even, then $C_{l_{2}}$ is a cycle with three real vertices.
If $d_{G}(u_{1})$ is odd, then we can obtain $C^{\prime}_{l_{2}}=C_{l_{2}}\cup
P^{1}$. It is clear that
$C^{\prime}_{l_{1}},C^{\prime}_{l_{2}}\in\mathcal{W}$. Similar to the above,
$p(G\Box H)\leq\frac{mn}{2}$.

If $l_{1}=3$ and $d_{G}(u_{1})$ is odd, then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{2},P^{1}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup\\{P^{2}\cup
C_{u_{2},u_{1}}\cup P^{1}\\}$ and $C^{\prime}_{l_{2}}=C_{u_{1},u_{2}}\cup
C_{l_{2}}$. It is clear that $C^{\prime}_{l_{2}}\in\mathcal{W}$. Similar to
the above, $p(G\Box H)\leq\frac{mn}{2}$. If $l_{1}=3$ and $d_{G}(u_{1})$ is
even, then $D\cup P^{2}$ is a member of $\mathcal{A}$. Thus, $G$ can be
decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1}\cup
P^{2}\\}\\}\\}\cup\\{\mathcal{L^{\prime}}\cup P^{\prime 1}\\}$ and
$D^{\prime}=D\cup P^{2}$. Suppose the number of real vertices of $D^{\prime}$
is $s$. By Lemma 3.1 and Theorem 4.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(D^{\prime}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s)}{2}+\frac{ns}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

Case 2. There exists no odd vertex in $C_{l_{1}}-u_{1}$.

If there are two odd vertices in $C_{l_{2}}-\\{v_{1}\\}$, then the proof is
similar to Subcase 1.2. If there is an odd vertex in $C_{l_{2}}-\\{v_{1}\\}$,
then the proof is similar to Subcase 1.3. We now suppose there is no odd
vertex in $C_{l_{2}}-\\{v_{1}\\}$ and consider the following subcases.

Subcase 2.1. There exist $u_{i},v_{j}\in U^{\prime}$ such that
$d_{G^{\prime}}(u_{i})\geq 2$ and $d_{G^{\prime}}(v_{j})\geq 2$.

It is fact that $u_{i}$ and $v_{j}$ are internal vertex of $P^{i}$ and $Q^{j}$
of $\mathcal{P}(G)$, respectively. Suppose that $P^{i}=P_{x,u_{i}}\cup
P_{u_{i},y}$, where $x$ and $y$ are the end vertices of $P^{i}$ and
$P_{x,u_{i}}$ and $P_{y,u_{i}}$ are the subpaths of $P^{i}$. Similarly,
$Q^{j}=Q_{z,v_{j}}\cup Q_{w,v_{j}}$. Now we obtain a virtual-real path
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{i},Q^{j}\\}\\}\cup\\{P_{x,u_{i}}\cup
C_{u_{i},u_{1}}\cup C_{u_{1},v_{j}}\cup Q_{z,v_{j}}\\}\cup\\{P_{y,u_{i}}\cup
C_{u_{1},u_{i}}\cup C_{v_{j},u_{1}}\cup Q_{w,v_{j}}\\}$ of $G$. By Theorem
1.3, $p(G\Box H)\leq\frac{mn}{2}$.

Subcase 2.2. There exist no $u_{i},v_{j}\in U^{\prime}$ such that
$d_{G^{\prime}}(u_{i})\geq 2$ and $d_{G^{\prime}}(v_{j})\geq 2$.

First, we consider the case of $max\\{l_{1},l_{2}\\}\geq 4$. Without loss of
generality, we suppose that $l_{1}\geq 4$. It is clear that $C_{l_{1}}$ is a
virtual-real cycle with $u_{1}$ being virtual. If $u_{1}$ is even in $G$, then
$C_{l_{2}}$ also a virtual-real cycle with $u_{1}$ being real. By Theorem 4.3,
$p(G\Box H)\leq\frac{mn}{2}$. Otherwise, $C_{l_{2}}\cup P^{1}$ is a member of
$\mathcal{W}$. By Lemma 4.1 and Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

Now we consider the case of $l_{1}=l_{2}=3$. If $u_{1}$ is even in $G$, then
$D\in\mathcal{A}$. Let
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{1}\\}\\}\cup\\{\mathcal{L^{\prime}}\cup P^{\prime 1}\\}$. By Lemma 3.1 and
Theorem 4.3, We have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(D\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-5)}{2}+\frac{5n}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

If $u_{1}$ is odd in $G$, then $u_{1}$ is virtual on $D$. To split $u_{1}$ to
$u_{11}$ and $u_{12}$, then both of them are virtual. We can obtain a virtual-
real cycle $C^{\prime}=u_{2}u_{3}u_{11}v_{3}v_{2}u_{12}$, where $u_{11}$ and
$u_{12}$ are virtual. By Lemma 2.2 and Corollary 4.2, we can obtain a path
decomposition of $C^{\prime}\boxdot H$ with $p(C^{\prime}\boxdot
H)=p(C_{4}\Box H)$. By Lemma 4.1 and Theorem 1.3, $p(G\Box
H)\leq\frac{mn}{2}$.

(2) $|N(C_{l_{1}})\cap N(C_{l_{2}})|\geq 2$.

Let $Q_{1}:=u_{1}u_{2}\cdots u_{t}=v_{1}v_{2}\cdots v_{t}$, where $2\leq t\leq
min\\{l_{1},l_{2}\\}$ be the shortest path from $u_{1}$ to $u_{t}$ in $G$.
Then $u_{1},\cdots,u_{t}$ are the common vertices of $C_{l_{1}}$ and
$C_{l_{2}}$. Let $U^{\prime}=U-\\{u_{1}u_{2}\cdots u_{t}\\}$. Let
$S=\\{x_{i}:x_{i}\in U^{\prime}\ and\ d_{G^{\prime}}(x_{i})\ is\ even\ and\
at\ least\ two\\}$, $\mathcal{L}=\\{P^{i}:x_{i}\in S\\}$ and
$\mathcal{L^{\prime}}=\\{P^{\prime i}:P^{i}\in\mathcal{L}\\}$. We consider the
following subcases.

Subcase 2.1. All vertices of $U^{\prime}$ are even in $G$.

Let $C=u_{t}u_{t+1}\cdots u_{l_{1}}u_{1}v_{l_{2}}v_{l_{2}-1}\cdots v_{t+1}$.
If both $u_{1}$ and $u_{t}$ are odd in $G^{\prime}$, then we can obtain a new
virtual-real path $Q^{\prime}_{1}=P^{1}\cup Q_{1}\cup P^{t}$, where $u_{1}$
and $u_{t}$ are virtual. Then we can obtain a virtual-real path cycle
decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1},P^{t}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup
Q^{\prime}_{1}\cup C$ of $G$. By Theorem 4.3, $p(G\Box H)\leq\frac{mn}{2}$.

If only one of $u_{1}$ and $u_{t}$ is odd in $G^{\prime}$, suppose $u_{1}$ is
odd, then we can obtain a new virtual-real path $Q^{\prime}_{1}=P^{1}\cup
Q_{1}$, where $u_{1}$ virtual and $u_{t}$ is real. Then
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1},P^{t}\\}\\}\\}\cup\mathcal{L^{\prime}}\cup
Q^{\prime}_{1}\cup P^{\prime t}\cup C$. By Theorem 4.3, $p(G\Box
H)\leq\frac{mn}{2}$.

If both $u_{1}$ and $u_{t}$ are even in $G^{\prime}$, then we will consider
the following two cases. If $|V(D)-V(Q_{1})|\geq 3$, then $Q_{1}$ is a new
path where $u_{1}$ and $u_{t}$ are real, and $C$ is a cycle with at least
three real vertices. Then
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1},P^{t}\\}\\}\cup\\{\mathcal{L^{\prime}}\cup\\{P^{\prime
1},P^{\prime t}\\}\\}\cup Q_{1}\cup C$. By Theorem 4.3, $p(G\Box
H)\leq\frac{mn}{2}$. If $|V(D)-V(Q_{1})|=2$, then
$D\in\\{\mathcal{B},\mathcal{F}\\}$. Let
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup\\{P^{1},P^{t}\\}\\}\cup\\{\mathcal{L^{\prime}}\cup\\{P^{\prime
1},P^{\prime t}\\}\\}$. By lemma 3.2, lemma 3.3 and Theorem 4.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(D\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-|D|)}{2}+\frac{n|D|}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

Subcase 2.2. At least two odd vertices in $U^{\prime}$.

Without loss of generality, we suppose $u_{l_{1}}$ and $v_{l_{2}}$ are odd in
$G$. If both $u_{1}$ and $u_{t}$ are odd in $G^{\prime}$, then we can obtain a
new virtual-real path $Q^{\prime}_{1}=P^{1}\cup Q_{1}\cup P^{t}$ where $u_{1}$
and $u_{t}$ are virtual. Then we can fined a virtual-real path decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{l_{1}},Q^{l_{2}},P^{1},P^{t}\\}\\}\cup\\{P^{l_{1}}\cup
C_{u_{l_{1}},u_{1}}\cup C_{v_{l_{2}},u_{1}}\\}\cup\\{Q^{l_{2}}\cup
C_{v_{t},v_{l_{2}}}\cup C_{u_{t},u_{l_{1}}}\\}\cup Q^{\prime}_{1}$ of $G$. By
Theorem 1.3, $p(G\Box H)\leq\frac{mn}{2}$.

If only one of $u_{1}$ and $u_{t}$ is odd in $G^{\prime}$, we suppose $u_{1}$
is odd, then we can obtain a new virtual-real path $Q^{\prime}_{1}=P^{1}\cup
Q_{1}$ where $u_{1}$ virtual is $u_{t}$ is real. Then
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{l_{1}},Q^{l_{2}},P^{1}\\}\\}\cup\\{P^{l_{1}}\cup
C_{u_{l_{1}},u_{1}}\cup C_{v_{l_{2}},u_{1}}\\}\cup\\{Q^{2}\cup
C_{v_{t},v_{l_{2}}}\cup C_{u_{t},u_{l_{1}}}\\}\cup Q^{\prime}_{1}$. By Theorem
1.3, $p(G\Box H)\leq\frac{mn}{2}$.

If both $u_{1}$ and $u_{t}$ are even in $G^{\prime}$, then $Q_{1}$ is a new
path. Then
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{l_{1}},Q^{l_{2}}\\}\\}\cup\\{P^{l_{1}}\cup
C_{u_{l_{1}},u_{1}}\cup C_{v_{l_{2}},u_{1}}\\}\cup\\{Q^{l_{2}}\cup
C_{v_{t},v_{l_{2}}}\cup C_{u_{t},u_{l_{1}}}\\}\cup Q_{1}$. By Theorem 1.3,
$p(G\Box H)\leq\frac{mn}{2}$.

Subcase 2.3. Only one odd vertex in $U^{\prime}$.

Without loss of generality, we suppose $u_{l_{1}}$ is odd in $G^{\prime}$. If
both $u_{1}$ and $u_{t}$ are odd in $G^{\prime}$, then we can fined a virtual-
real path decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{1},P^{t},P^{l_{1}}\\}\\}\cup\\{P^{1}\cup
C_{u_{1},u_{l_{1}}}\\}\cup\\{P^{l_{1}}\cup C_{u_{l_{1}},u_{1}}\cup
C_{v_{t},v_{1}}\cup P^{t}\\}$. By Theorem 1.3, $p(G\Box H)\leq\frac{mn}{2}$.

If only one of $u_{1}$ and $u_{t}$ is odd in $G^{\prime}$, suppose $u_{1}$ is
odd in $G$, then we can fined a virtual-real path decomposition
$\mathcal{F}(G)=\\{\mathcal{F}(G^{\prime})\setminus\\{P^{1},P^{l_{1}}\\}\\}\cup\\{P^{1}\cup
C_{u_{1},u_{l_{1}}}\\}\cup\\{P^{l_{1}}\cup C_{u_{l_{1}},u_{1}}\cup
C_{v_{t},v_{1}}\\}$. By Theorem 1.3, $p(G\Box H)\leq\frac{mn}{2}$.

If both $u_{1}$ and $u_{t}$ are even in $G^{\prime}$, then $Q_{1}$ is a new
path. Let $G^{\prime\prime}=G^{\prime}+Q_{1}$ and $D^{\prime}=\\{D\setminus
Q_{1}\\}\cup P^{l_{1}}$. If $|V(D)-V(Q_{1})|\geq 3$, then
$D^{\prime}\in\\{\mathcal{W}\\}$. Let
$\mathcal{F}(G^{\prime\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{l_{1}}\\}\\}\cup\\{\mathcal{L^{\prime}}\\}\cup Q_{1}$. Then the graph $G$
can been decompose into $\mathcal{F}(G^{\prime\prime})$ and $D^{\prime}$.
Suppose the number of real vertices of $D^{\prime}$ is $s$, by Lemma 4.1 and
Theorem 1.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F}(G^{\prime\prime})}p(P\boxdot
H)+p(D^{\prime}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s)}{2}+\frac{ns}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

If $|V(D)-V(Q_{1})|=2$, then $D\cup
P^{l_{1}}\in\\{\mathcal{B},\mathcal{F}\\}$. Let $D^{\prime\prime}=D\cup
P^{l_{1}}$. Then $G$ can be decomposed into
$\mathcal{F^{\prime}}(G^{\prime})=\\{\mathcal{F}(G^{\prime})\setminus\\{\mathcal{L}\cup
P^{l_{1}}\\}\\}\cup\mathcal{L^{\prime}}$ and $D^{\prime\prime}$. Suppose the
number of real vertices of $D^{\prime\prime}$ is $s$, by Lemma 3.2, Lemma 3.3
and Theorem 1.3, we have

$\displaystyle p(G\Box H)$ $\displaystyle\leq$
$\displaystyle\sum_{P\in\mathcal{F^{\prime}}(G^{\prime})}p(P\boxdot
H)+p(D^{\prime\prime}\boxdot H)$ $\displaystyle\leq$
$\displaystyle\frac{n(m-s)}{2}+\frac{ns}{2}$ $\displaystyle=$
$\displaystyle\frac{mn}{2}.$

∎

Data availability statement

Data sharing not applicable to this article as no data sets were generated or
analysed during the current study.

Declarations of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] S.E. Anderson, K. Kuenzel, Power domination in cubic graphs and Cartesian products, Discrete Math. 345 (2022) 113113.
  * [2] M. Azari, N. Dehgardi, T. Došlić, Lower bounds on the irregularity of trees and unicyclic graphs, Discrete Appl. Math. 324 (2023) 136-144.
  * [3] S. Barik, S. Behera, On the smallest positive eigenvalue of bipartite unicyclic graphs with a unique perfect matching, Discrete Math. 346 (2023) 113252.
  * [4] M. Bonamy, T.J. Perrett, Gallai’s path decomposition conjecture for graphs of small maximum degree, Discrete Math. 342 (2019) 1293-1299.
  * [5] J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, 2008.
  * [6] F. Botler, A. Jiménez, On path decompositions of $2k$-regular graphs, Discrete Math. 340 (2017) 1405-1411.
  * [7] F. Botler, A. Jiménez, M. Sambinelli, Gallai’s path decomposition conjecture for triangle-free planar graphs, Discrete Math. 342 (2019) 1403-1414.
  * [8] F. Botler, M. Sambinelli, Towards Gallai’s path decomposition conjecture, J. Graph Theory 97(1) (2020) 161-184.
  * [9] F. Botler, M. Sambinelli, R.S. Coelho, O. Lee, Gallai’s path decomposition conjecture for graphs with treewidth at most 3, J. Graph Theory 93(3) (2020) 328-349.
  * [10] X. Chen, B. Wu, Galli’s path decomposition conjecture for cartesian product of graphs, 2023, submitted for publication. ArXiv e-prints arXiv: 2310.11189.
  * [11] Y. Chu, G. Fan, Q. Liu, On Gallai’s conjecture for graphs with maximum degree 6, Discrete Math. 344(2) (2021) 112212.
  * [12] Y. Chu, G. Fan, C. Zhou, Path decomposition of triangle-free graphs, Discrete Math. 345 (2022) 112866.
  * [13] N. Dean, M. Kouider, Gallai’s conjecture for disconnected graphs, Discrete Math. 213 (2000) 43-54.
  * [14] A. Donald, An upper bound for the path number of a graph, J. Graph Theory 4 (1980) 189-201.
  * [15] M. Eliasi, Unicyclic and bicyclic graphs with maximum exponential second Zagreb index, Discrete Appl. Math. 307 (2022) 172-179.
  * [16] A.P. Ezhilarasi, A. Muthusamy, Decomposition of Cartesian product of complete graphs into paths and stars with four edges, Comment. Math. Univ. Carolin. 62 (3) (2021) 273-289.
  * [17] G. Fan, Path decompositions and Gallai’s conjecture, J. Combin. Theory Ser. B 93 (2) (2005) 117-125.
  * [18] X. Geng, M. Fang, D. Li, Gallai’s conjecture for outerplanar graphs, J. Interdiscip. Math. 18 (5) (2015) 593-598.
  * [19] R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2011.
  * [20] P. Harding, S. McGuinness, Gallai’s conjecture for graphs of girth at least four, J. Graph Theory 75 (2014) 256-274.
  * [21] W. Imrich, I. Peterin, Recognizing Cartesian products in linear time, Discrete Math. 307 (2007) 472-483.
  * [22] W. Imrich, S. Klavžar, D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product, A K Peters, Wellesley, MA, 2008.
  * [23] S. Jeevadoss, A. Muthusamy, Decomposition of product graphs into paths and cycles of length four, Graphs Combin. 32 (2016) 199-223.
  * [24] A. Jiménez, Y. Wakabayashi, On path-cycle decompositions of triangle-free graphs, Discrete Math. Theor. Comput. Sci. 19 (3) (2017) Paper No. 7, 21.
  * [25] H. Kaul, J.A. Mudrock, G. Sharma, Q. Stratton, DP-coloring Cartesian products of graphs, J. Graph Theory 103 (2023) 285-306.
  * [26] P. Li, A. Yu, R. Hao, On the $D_{\alpha}$-spectral radius of cacti and bicyclic graphs, Discrete Math. 346 (2023) 113134.
  * [27] G. Liu, K. Deng, The maximum Mostar indices of unicyclic graphs with given diameter, Appl. Math. Comput. 439 (2023) 127636.
  * [28] L. Lovász, On covering of graphs, in: P. Erdős, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231-236.
  * [29] O. Oyewumi, A.D. Akwu, T.I. Azer, Path decomposition of certain graphs, Open J. Discret. Appl. Math. 1 (1) (2018) 26-32.
  * [30] L. Pyber, Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1) (1996) 152-159.
  * [31] D.F. Rall, On well-dominated direct, Cartesian and strong product graphs, Discrete Math. 346 (2023) 113178.
  * [32] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457.
  * [33] L. Yan, On path decompositions of graphs, Ph.D. Thesis, Arizona State University, 1998.