* [67] L. Liu, Y. Liao, Y. Wang, A. Geiger, and Y. Liu, “Learning steering kernels for guided depth completion,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 2850–2861, 2021.
  * [68] L. Liu, X. Song, X. Lyu, J. Diao, M. Wang, Y. Liu, and L. Zhang, “Fcfr-net: Feature fusion based coarse-to-fine residual learning for depth completion,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 35, no. 3, 2021, pp. 2136–2144.
  * [69] S. Liu, S. De Mello, J. Gu, G. Zhong, M.-H. Yang, and J. Kautz, “Learning affinity via spatial propagation networks,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 1520–1530.
  * [70] Y. Long, H. Yu, and B. Liu, “Depth completion towards different sensor configurations via relative depth map estimation and scale recovery,” _Journal of Visual Communication and Image Representation_ , vol. 80, p. 103272, 2021.
  * [71] A. Lopez-Rodriguez, B. Busam, and K. Mikolajczyk, “Project to adapt: Domain adaptation for depth completion from noisy and sparse sensor data,” in _Asian Conference on Computer Vision (ACCV)_ , 2020.
  * [72] H. Lu, S. Xu, and S. Cao, “Sgtbn: Generating dense depth maps from single-line lidar,” _IEEE Sensors Journal_ , vol. 21, no. 17, pp. 19 091–19 100, 2021\.
  * [73] K. Lu, N. Barnes, S. Anwar, and L. Zheng, “From depth what can you see? depth completion via auxiliary image reconstruction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020, pp. 11 303–11 312.
  * [74] S. Lu, X. Ren, and F. Liu, “Depth enhancement via low-rank matrix completion,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2014, pp. 3390–3397.
  * [75] F. Ma, L. Carlone, U. Ayaz, and S. Karaman, “Sparse depth sensing for resource-constrained robots,” _The International Journal of Robotics Research_ , vol. 38, no. 8, pp. 935–980, 2019.
  * [76] F. Ma, G. V. Cavalheiro, and S. Karaman, “Self-supervised sparse-to-dense: Self-supervised depth completion from lidar and monocular camera,” in _International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 3288–3295.
  * [77] F. Ma and S. Karaman, “Sparse-to-dense: Depth prediction from sparse depth samples and a single image,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 4796–4803.
  * [78] X. Mao, C. Shen, and Y.-B. Yang, “Image restoration using very deep convolutional encoder-decoder networks with symmetric skip connections,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [79] J. Masci, J. Angulo, and J. Schmidhuber, “A learning framework for morphological operators using counter–harmonic mean,” in _International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing_ , 2013, pp. 329–340.
  * [80] J. McCormac, A. Handa, S. Leutenegger, and A. J. Davison, “Scenenet rgb-d: 5m photorealistic images of synthetic indoor trajectories with ground truth,” _arXiv preprint arXiv:1612.05079_ , 2016.
  * [81] D. Miao, J. Fu, Y. Lu, S. Li, and C. W. Chen, “Texture-assisted kinect depth inpainting,” in _2012 IEEE International Symposium on Circuits and Systems (ISCAS)_. IEEE, 2012, pp. 604–607.
  * [82] C. Murdock, M. Chang, and S. Lucey, “Deep component analysis via alternating direction neural networks,” in _European Conference on Computer Vision (ECCV)_ , 2018, pp. 820–836.
  * [83] E. Nadaraya, “On estimating regression,” _Theory of Probability and Its Applications_ , vol. 9, pp. 141–142, 1964.
  * [84] H. Niederreiter, “Random number generation and quasi-monte carlo methods,” _SIAM_ , vol. 35, no. 4, pp. 680–681, 1993.
  * [85] A. B. Owen, “A robust hybrid of lasso and ridge regression,” _Contemporary Mathematics_ , vol. 443, no. 7, pp. 59–72, 2007.
  * [86] J. Park, K. Joo, Z. Hu, C.-K. Liu, and I. So Kweon, “Non-local spatial propagation network for depth completion,” in _European Conference on Computer Vision (ECCV)_ , 2020, pp. 120–136.
  * [87] T. Park, M.-Y. Liu, T.-C. Wang, and J.-Y. Zhu, “Semantic image synthesis with spatially-adaptive normalization,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR)_ , 2019, pp. 2337–2346.
  * [88] J. Qiu, Z. Cui, Y. Zhang, X. Zhang, S. Liu, B. Zeng, and M. Pollefeys, “Deeplidar: Deep surface normal guided depth prediction for outdoor scene from sparse lidar data and single color image,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 3308–3317.
  * [89] C. Qu, T. Nguyen, and C. Taylor, “Depth completion via deep basis fitting,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2020, pp. 71–80.
  * [90] L. Reichardt, P. Mangat, and O. Wasenmüller, “Dvmn: Dense validity mask network for depth completion,” in _IEEE International Intelligent Transportation Systems Conference (ITSC)_ , 2021, pp. 2653–2659.
  * [91] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _International Conference on Medical image computing and computer-assisted intervention (MICCAI)_ , 2015, pp. 234–241.
  * [92] G. Ros, L. Sellart, J. Materzynska, D. Vazquez, and A. M. Lopez, “The synthia dataset: A large collection of synthetic images for semantic segmentation of urban scenes,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 3234–3243.
  * [93] K. Ryu, K.-i. Lee, J. Cho, and K.-J. Yoon, “Scanline resolution-invariant depth completion using a single image and sparse lidar point cloud,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 6961–6968, 2021\.
  * [94] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR)_ , 2018, pp. 4510–4520.
  * [95] R. Schuster, O. Wasenmuller, C. Unger, and D. Stricker, “Ssgp: Sparse spatial guided propagation for robust and generic interpolation,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2021, pp. 197–206.
  * [96] D. Senushkin, M. Romanov, I. Belikov, N. Patakin, and A. Konushin, “Decoder modulation for indoor depth completion,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 2181–2188.
  * [97] J. Shen and S.-C. S. Cheung, “Layer depth denoising and completion for structured-light rgb-d cameras,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2013, pp. 1187–1194.
  * [98] S. S. Shivakumar, T. Nguyen, I. D. Miller, S. W. Chen, V. Kumar, and C. J. Taylor, “Dfusenet: Deep fusion of rgb and sparse depth information for image guided dense depth completion,” in _IEEE Intelligent Transportation Systems Conference (ITSC)_ , 2019, pp. 13–20.
  * [99] N. Silberman, D. Hoiem, P. Kohli, and R. Fergus, “Indoor segmentation and support inference from rgbd images,” in _European Conference on Computer Vision (ECCV)_ , vol. 7576, 2012, pp. 746–760.
  * [100] Z. Song, J. Lu, Y. Yao, and J. Zhang, “Self-supervised depth completion from direct visual-lidar odometry in autonomous driving,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * [101] R. A. M. Strudel, R. G. Pinel, I. Laptev, and C. Schmid, “Segmenter: Transformer for semantic segmentation,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021, pp. 7242–7252.
  * [102] H. Su, V. Jampani, D. Sun, S. Maji, E. Kalogerakis, M.-H. Yang, and J. Kautz, “Splatnet: Sparse lattice networks for point cloud processing,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 2530–2539.
  * [103] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 1–9.
  * [104] J. Tang, F.-P. Tian, W. Feng, J. Li, and P. Tan, “Learning guided convolutional network for depth completion,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 1116–1129, 2021.
  * [105] Z. Tao, P. Shuguo, Z. Hui, and S. Yingchun, “Dilated u-block for lightweight indoor depth completion with sobel edge,” _IEEE Signal Processing Letters_ , vol. 28, pp. 1615–1619, 2021.
  * [106] L. Teixeira, M. R. Oswald, M. Pollefeys, and M. Chli, “Aerial single-view depth completion with image-guided uncertainty estimation,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1055–1062, 2020.
  * [107] C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 1998, pp. 839–846.
  * [108] Y. Tsuji, H. Chishiro, and S. Kato, “Non-guided depth completion with adversarial networks,” in _International Conference on Intelligent Transportation Systems (ITSC)_ , 2018, pp. 1109–1114.
  * [109] J. Uhrig, N. Schneider, L. Schneider, U. Franke, T. Brox, and A. Geiger, “Sparsity invariant cnns,” in _International Conference on 3D Vision (3DV)_ , 2017, pp. 11–20.
  * [110] W. Van Gansbeke, D. Neven, B. De Brabandere, and L. Van Gool, “Sparse and noisy lidar completion with rgb guidance and uncertainty,” in _International Conference on Machine Vision Applications (MVA)_ , 2019, pp. 1–6.
  * [111] X. Cheng, P. Wang, and R. Yang, “Learning depth with convolutional spatial propagation network,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 42, pp. 2361–2379, 2020.
  * [112] A. Eldesokey, M. Felsberg, and F. S. Khan, “Confidence propagation through cnns for guided sparse depth regression,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 42, no. 10, pp. 2423–2436, 2019\.
  * [113] K. Lu, N. Barnes, S. Anwar, and L. Zheng, “Depth completion auto-encoder,” in _IEEE/CVF Winter Conference on Applications of Computer Vision Workshops (WACVW)_ , 2022, pp. 63–73.
  * [114] S. Wang, S. Suo, W.-C. Ma, A. Pokrovsky, and R. Urtasun, “Deep parametric continuous convolutional neural networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 2589–2597.
  * [115] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, “Dynamic graph cnn for learning on point clouds,” _ACM Transactions on Graphics (TOG)_ , vol. 38, pp. 1 – 12, 2019.
  * [116] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” _IEEE transactions on image processing_ , vol. 13, no. 4, pp. 600–612, 2004.
  * [117] D. Wofk, F. Ma, T.-J. Yang, S. Karaman, and V. Sze, “Fastdepth: Fast monocular depth estimation on embedded systems,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 6101–6108.
  * [118] A. Wong, S. Cicek, and S. Soatto, “Learning topology from synthetic data for unsupervised depth completion,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 1495–1502, 2021.
  * [119] A. Wong, X. Fei, B.-W. Hong, and S. Soatto, “An adaptive framework for learning unsupervised depth completion,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 3120–3127, 2021.
  * [120] A. Wong, X. Fei, S. Tsuei, and S. Soatto, “Unsupervised depth completion from visual inertial odometry,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1899–1906, 2020.
  * [121] A. Wong and S. Soatto, “Unsupervised depth completion with calibrated backprojection layers,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021, pp. 12 747–12 756.
  * [122] X. Xiong, H. Xiong, K. Xian, C. Zhao, Z. Cao, and X. Li, “Sparse-to-dense depth completion revisited: Sampling strategy and graph construction,” in _European Conference on Computer Vision (ECCV)_ , 2020.
  * [123] Y. Xu, X. Zhu, J. Shi, G. Zhang, H. Bao, and H. Li, “Depth completion from sparse lidar data with depth-normal constraints,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019, pp. 2811–2820.
  * [124] Z. Xu, H. Yin, and J. Yao, “Deformable spatial propagation networks for depth completion,” in _IEEE International Conference on Image Processing (ICIP)_ , 2020, pp. 913–917.
  * [125] L. Yan, K. Liu, and E. Belyaev, “Revisiting sparsity invariant convolution: A network for image guided depth completion,” _IEEE Access_ , vol. 8, pp. 126 323–126 332, 2020.
  * [126] L. Yan, K. Liu, and L. Gao, “Dan-conv: Depth aware non-local convolution for lidar depth completion,” _Electronics Letters_ , vol. 57, no. 20, pp. 754–757, 2021.
  * [127] Z. Yan, K. Wang, X. Li, Z. Zhang, B. Xu, J. Li, and J. Yang, “Rignet: Repetitive image guided network for depth completion,” _arXiv preprint arXiv:2107.13802_ , 2021.
  * [128] X. Yang, W. Liu, D. Tao, and J. Cheng, “Canonical correlation analysis networks for two-view image recognition,” _Information Sciences_ , vol. 385, pp. 338–352, 2017.
  * [129] Y. Yang, A. Wong, and S. Soatto, “Dense depth posterior (ddp) from single image and sparse range,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 3353–3362.
  * [130] W. Yin, Y. Liu, C. Shen, and Y. Yan, “Enforcing geometric constraints of virtual normal for depth prediction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 5684–5693.
  * [131] S. Yoon and A. Kim, “Balanced depth completion between dense depth inference and sparse range measurements via kiss-gp,” _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 10 468–10 475, 2020\.
  * [132] Z. You, Y.-H. Tsai, W.-C. Chiu, and G. Li, “Towards interpretable deep networks for monocular depth estimation,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 12 879–12 888.
  * [133] Q. Yu, L. Chu, Q. Wu, and L. Pei, “Grayscale and normal guided depth completion with a low-cost lidar,” in _IEEE International Conference on Image Processing (ICIP)_ , 2021, pp. 979–983.
  * [134] C. Zhang, Y. Tang, C. Zhao, Q. Sun, Z. Ye, and J. Kurths, “Multitask gans for semantic segmentation and depth completion with cycle consistency,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 12, pp. 5404–5415, 2021.
  * [135] Y. Zhang, T. Nguyen, I. D. Miller, S. S. Shivakumar, S. Chen, C. J. Taylor, and V. Kumar, “Dfinenet: Ego-motion estimation and depth refinement from sparse, noisy depth input with rgb guidance,” _arXiv preprint arXiv:1903.06397_ , 2019.
  * [136] Y. Zhang and T. Funkhouser, “Deep depth completion of a single rgb-d image,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 175–185.
  * [137] Y. Zhang, P. Wei, H. Li, and N. Zheng, “Multiscale adaptation fusion networks for depth completion,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2020, pp. 1–7.
  * [138] Y. Zhang, P. Wei, and N. Zheng, “A multi-cue guidance network for depth completion,” _Neurocomputing_ , vol. 441, pp. 291–299, 2021.
  * [139] Z. Zhang, X. Lu, G. Cao, Y. Yang, L. Jiao, and F. Liu, “Vit-yolo: Transformer-based yolo for object detection,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021, pp. 2799–2808.
  * [140] S. Zhao, M. Gong, H. Fu, and D. Tao, “Adaptive context-aware multi-modal network for depth completion,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 5264–5276, 2021.
  * [141] Y. Zhong, C.-Y. Wu, S. You, and U. Neumann, “Deep rgb-d canonical correlation analysis for sparse depth completion,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 5332–5342.
  * [142] Z. Zhou, M. M. R. Siddiquee, N. Tajbakhsh, and J. Liang, “Unet++: Redesigning skip connections to exploit multiscale features in image segmentation,” _IEEE transactions on medical imaging_ , vol. 39, no. 6, pp. 1856–1867, 2019\.
  * [143] X. Zhu, H. Hu, S. Lin, and J. Dai, “Deformable convnets v2: More deformable, better results,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 9308–9316.
  * [144] Y. Zhu, W. Dong, L. Li, J. Wu, X. Li, and G. Shi, “Robust depth completion with uncertainty-driven loss functions,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , 2022.
  * [145] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learning transferable architectures for scalable image recognition,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 8697–8710.

|  Junjie Hu (Member, IEEE) received the M.S. and Ph.D. degrees from the
Graduate School of Information Science, Tohoku University, Sendai, Japan, in
2017 and 2020, respectively. He is currently a Research Scientist with the
Shenzhen Institute of Artificial Intelligence and Robotics for Society. His
research interests include machine learning, computer vision, and robotics.
---|---
|  Chenyu Bao received the B.Eng degree from the School of Mechanical Science
and Engineering, HuaZhong University of Science and Technology in 2022. He is
currently a graduate student in the School of Science and Engineering, Chinese
University of Hong Kong, Shenzhen. His research interests include computer
vision and robot perception.
---|---
|  Mete Ozay (M’09) received the B.Sc., M.Sc., Ph.D. degrees in mathematical
physics, information systems, and computer engineering & science from METU,
Turkey. He has been a visiting Ph.D. and fellow in the Princeton University,
USA, a research fellow in the University of Birmingham, UK, and an Assistant
Professor in the Tohoku University, Japan. His current research interests
include pure and applied mathematics, theoretical computer science &
neuroscience.
---|---
|  Chenyou Fan serves as Associate Profession of the School of Artificial
Intelligence, South China Normal University, China. He received the B.S.
degree in computer science from the Nanjing University, China, in 2011, and
the M.S. and Ph.D. degrees from Indiana University, USA, in 2014 and 2019,
respectively. His research interests include machine learning and computer
vision. He served in the program committee of CVPR, NeurIPS, ACM MM and top AI
journals for more than 20 times.
---|---
|  Qing Gao received his Ph.D. degree in the State Key Laboratory of Robotics,
Shenyang Institute of Automation (SIA), Chinese Academy of Sciences (CAS),
Shenyang, China, in 2020. He is currently a Research Scientist with the
Shenzhen Institute of Artificial Intelligence and Robotics for Society. His
research interests include robotics, artificial intelligence, machine vision
and human–robot interaction.
---|---
|  Honghai Liu (Fellow, IEEE) received the Ph.D. degree in intelligent
robotics from King’s College London, London, U.K., in 2003. He is a Professor
with the Harbin Institute of Technology (Shenzhen), Shenzhen, China. He is
also a Chair Professor of Human–Machine Systems with the University of
Portsmouth, Portsmouth, U.K. His research interests include multi-sensory data
fusion, pattern recognition, intelligent video analytics, intelligent
robotics, and their practical applications. He is an Associate Editor of the
IEEE Transactions on Industrial Electronics, the IEEE Transactions on
Industrial Informatics, and the IEEE Transactions on Cybernetics.
---|---
|  Tin Lun Lam (Senior Member, IEEE) received the B.Eng. (First Class Hons.)
and Ph.D. degrees in robotics and automation from the Chinese University of
Hong Kong, Hong Kong, in 2006 and 2010, respectively. He is currently an
Assistant Professor with the Chinese University of Hong Kong, Shenzhen, China,
and the Director of Center for the Intelligent Robots, Shenzhen Institute of
Artificial Intelligence and Robotics for Society. He has authored or
coauthored two monographs and more than 50 research papers in top-tier
international journals and conference proceedings in robotics and AI. His
research interests include multirobot systems, field robotics, and
collaborative robotics.
---|---


# Laplacian Spectra of Regular Graph Transformations ††thanks: Aiping Deng and
Juan Meng are supported in part by the Fundamental Research Funds for the
Central Universities of China 11D10902 and 11D10913.

Aiping Denga111Corresponding author. Email<EMAIL_ADDRESS>Tel:
86-21-67792089-568. Fax: 86-21-67792311  , Alexander Kelmansb,c, Juan Menga
aDepartment of Applied Mathematics, Donghua University, 201620 Shanghai, China
bDepartment of Mathematics, University of Puerto Rico, San Juan, PR, United
States
cDepartment of Mathematics, Rutgers University, New Brunswick, NJ, United
States

###### Abstract

Given a graph $G$ with vertex set $V(G)=V$ and edge set $E(G)=E$, let $G^{l}$
be the line graph and $G^{c}$ the complement of $G$. Let $G^{0}$ be the graph
with $V(G^{0})=V$ and with no edges, $G^{1}$ the complete graph with the
vertex set $V$, $G^{+}=G$ and $G^{-}=G^{c}$. Let $B(G)$ ($B^{c}(G)$) be the
graph with the vertex set $V\cup E$ and such that $(v,e)$ is an edge in $B(G)$
(resp., in $B^{c}(G)$) if and only if $v\in V$, $e\in E$ and vertex $v$ is
incident (resp., not incident) to edge $e$ in $G$. Given
$x,y,z\in\\{0,1,+,-\\}$, the ${xyz}$-transformation $G^{xyz}$ of $G$ is the
graph with the vertex set $V(G^{xyz})=V\cup E$ and the edge set
$E(G^{xyz})=E(G^{x})\cup E((G^{l})^{y})\cup E(W)$, where $W=B(G)$ if $z=+$,
$W=B^{c}(G)$ if $z=-$, $W$ is the graph with $V(W)=V\cup E$ and with no edges
if $z=0$, and $W$ is the complete bipartite graph with parts $V$ and $E$ if
$z=1$. In this paper we obtain the Laplacian characteristic polynomials and
some other Laplacian parameters of every $xyz$-transformation of an
$r$-regular graph $G$ in terms of $|V|$, $r$, and the Laplacian spectrum of
$G$.
Key words: regular graph, $xyz$-transformation, Laplacian spectrum, Laplacian
characteristic polynomial.
AMS Subject Classification: 05C31,05C50, 05C76

##  1 Introduction

The graphs in this paper are simple and undirected. All notions on graphs and
matrices that are used but not defined here can be found in [1, 5, 6, 8, 22].
Let ${\cal G}$ denote the set of simple undirected graphs. Various important
results in graph theory have been obtained by considering some functions
$F:{\cal G}\to{\cal G}$ or $F_{s}:{\cal G}_{1}\times\ldots\times{\cal
G}_{s}\to{\cal G}$ called operations or transformations (here each ${\cal
G}_{i}={\cal G}$) and by establishing how these operations affect certain
properties or parameters of graphs. The complement, the $k$-th power of a
graph, and the line graph are well known examples of such operations. The
Bondy-Chvátal and Ryzác̆ek closers of graphs are very useful operations in
graph Hamiltonicity theory [1]. (Strengthenings and extensions of the Ryzác̆ek
result are given in [9]). Some graph operations introduced by A. Kelmans (see,
in particular, [10, 13]) turn out to be monotone with respect to various
partial order relations on the set of graphs. For that reason these operations
turned out to be very useful in obtaining non-trivial results on graphs of
given size with various extreme properties (with the maximum number of
spanning trees and some other Laplacian parameters of graphs, with the maximum
reliability of graphs having randomly deleted edges, etc.), see, for example,
[11, 12]. The operation of voltage lifting on a base graph introduced by Gross
and Tucker can be generalized to digraphs [4, 7]. Using this operation one can
obtain the derived covering (di)graph and deduce the relationship between the
adjacency characteristic polynomials of the base (di)graph and its derived
covering (di)graph [4, 3, 19, 25].
In this paper we consider certain graph operations depending on parameters
$x,y,z\in\\{0,1,+,-\\}$. These operations induce functions $T^{xyz}:{\cal
G}\to{\cal G}$. We put $T^{xyz}(G)=G^{xyz}$ and call $G^{xyz}$ the
$xyz$-transformation of $G$. We describe for all $x,y,z\in\\{0,1,+,-\\}$ the
Laplacian characteristic polynomials and some other Laplacian parameters of
$xyz$-transformations of an $r$-regular graph $G$. This descriptions revealed
the following fact interesting in itself: if $G$ is $r$-regular, then the
Laplacian spectrum of $G^{xyz}$ is uniquely defined by $|V(G)|$, $r$, and the
Laplacian spectrum of $G$; moreover, the Laplacian eigenvalues are the roots
of a quadratic polynomial with the coefficients depending on $|V(G)|$, $r$,
and the Laplacian spectrum of $G$. Furthermore, for
$(xyz)\in\\{(00+),(0++),(+0+)\\}$ the number of spanning trees of $G^{xyz}$
are uniquely defined by $|V(G)|$, $r$, and the number of spanning trees of $G$
(see Theorem 2.5 and Corollaries 3.5, 3.9, and 3.12 below). The approach we
have used to obtain all these formulas may also be useful in further research
along this line. The results of this paper may be considered as a natural and
useful extension of Section 2 “Operations on Graphs and the Resulting Spectra”
in book [2].

The Reciprocity Theorem [16] (see also Theorem 2.6 below) provides for every
graph $G$ the relation between the Laplacian characteristic polynomial of $G$
and its complement $G^{c}$. For that reason it is sufficient to describe the
Laplacian characteristic polynomials of graph $xyz$-transformations up to the
graph operation of taking the complement.
In Section 2 we introduce main notions, notation, simple observations, and
some preliminaries. In Section 3 we describe (up to the complementarity) the
Laplacian characteristic polynomials of the transformations $G^{xyz}$ with
$\\{x,y,z\\}\cap\\{0,1\\}\neq\emptyset$. In Section 4 we describe the
Laplacian characteristic polynomials of transformations $G^{xyz}$ with
$\\{x,y,z\\}\cap\\{0,1\\}=\emptyset$, i.e. with $x,y,z\in\\{+,-\\}$. In
Sections 5 we consider some transformations of cycles and show that different
transformations of the same graph may be isomorphic. Section 6 contains some
additional remarks. In the Appendix we provide for all $x,y,z\in\\{0,1,+,-\\}$
the list of formulas for the Laplacian characteristic polynomials and the
number of spanning trees of the $(xyz)$-transformations of an $r$-regular
graph $G$ in terms of $r$, the number of vertices, the number of edges, and
the Laplacian spectrum of $G$. This catalog may be pretty useful for further
research in the spectrum graph theory.

##  2 Some notions, notation, and preliminaries

Let $G=(V,E)$ be a graph with vertex set $V=V(G)$ and edge set $E=E(G)$. Let
$v(G)=|V(G)|$ and $e(G)=|E(G)|$. The degree $d(v,G)$ of vertex $v\in V$ is the
number of vertices in $G$ adjacent to $v$. Let $t(G)$ denote the number of
spanning trees of $G$.

Given two graphs $G$ and $H$, an isomorphism from $G$ to $H$ is a bijection
$\alpha$ from $V(G)$ to $V(H)$ such that $(u,v)\in
E(G)\Leftrightarrow(\alpha(u),\alpha(v))\in E(H)$.

The complement $G^{c}$ of a graph $G$ is the graph with vertex set
$V(G^{c})=V(G)$ and $(u,v)\in E(G^{c})\Leftrightarrow(u,v)\not\in E(G)$ for
any $u,v\in V(G)$ and $u\neq v$.

The line graph $G^{l}$ of a graph $G$ is the graph with vertex set $E(G)$ and
two vertices are adjacent in $G^{l}$ if and only if the corresponding edges in
$G$ are adjacent. Graphs $G$ and $H$ are called isomorphic if there exists an
isomorphism from $G$ to $H$.
For a graph $G=(V,E)$, let $G^{0}$ be the graph with $V(G^{0})=V$ and with no
edges, $G^{1}$ the complete graph with $V(G^{1})=V$, $G^{+}=G$, and
$G^{-}=G^{c}$. Let $B(G)$ ($B^{c}(G)$) be the graph with the vertex set $V\cup
E$ and such that $(v,e)$ is an edge in $B(G)$ (resp., in $B^{c}(G)$) if and
only if $v\in V$, $e\in E$, and vertex $v$ is incident (resp., not incident)
to edge $e$ in $G$. For example, in Figure 1, $G^{00+}=B(G)$ and $B^{c}(G)$ is
obtained from $G^{01-}$ by deleting the edge connecting two white vertices.
The graph transformations we are going to discuss are defined as follows.

######  Definition 2.1.

Given a graph $G=(V,E)$ and three variables $x,y,z\in\\{0,1,+,-\\}$, the
${xyz}$-transformation $G^{xyz}$ of $G$ is the graph with the vertex set
$V(G^{xyz})=V\cup E$ and the edge set $E(G^{xyz})=E(G^{x})\cup
E((G^{l})^{y})\cup E(W)$, where $W=B(G)$ if $z=+$, $W=B^{c}(G)$ if $z=-$, $W$
is the graph with $V(W)=V\cup E$ and with no edges if $z=0$, and $W$ is the
complete bipartite graph with parts $V$ and $E$ if $z=1$.

Figure 1: Some $xyz$-transformations of a 3-vertex path.

Examples of ${xyz}$-transformations of a 3-vertex path are given in Figure 1.
Graphs $G^{+++}$ and $G^{00+}$ are called in [2] the total graph and the
subdivision graph of $G$, respectively.
Let $G$ be a graph with vertex set $V=\\{v_{1},\ldots,v_{n}\\}$ and edge set
$E=\\{e_{1},\ldots,e_{m}\\}$. The incidence matrix $Q(G)$ of $G$ is the
$(V\times E)$-matrix $\\{q_{ij}\\}$, where $q_{ij}=1$ if vertex $v_{i}$ is
incident to edge $e_{j}$ and $q_{ij}=0$, otherwise. Let $A(G)$ be the
$(V\times V)$-matrix $\\{a_{ij}\\}$, where $a_{ij}=1$ if $(v_{i},v_{j})\in E$
and $a_{ij}=0$, otherwise. Let $D(G)$ be the (diagonal) $(V\times V)$-matrix
$\\{d_{ij}\\}$, where $d_{ii}=d(v_{i},G)$ and $d_{ij}=0$ for $i\neq j$. The
matrices $A(G)$, $D(G)$ and $L(G)=D(G)-A(G)$ are called the adjacency matrix,
the degree matrix, and the Laplacian matrix of $G$, respectively. The
adjacency polynomial, the adjacency spectrum and the adjacency eigenvalues of
$G$ are the characteristic polynomial $A(\alpha,G)=\det(\alpha I-A(G))$, the
spectrum, and the eigenvalues of $A(G)$, respectively. Similarly, the
Laplacian polynomial, the Laplacian spectrum and the Laplacian eigenvalues of
$G$ are the characteristic polynomial $L(\lambda,G)=\det(\lambda I-L(G))$, the
spectrum, and the eigenvalues of $L(G)$, respectively. Let $I_{n}$ be the
identity $(n\times n)$-matrix and $J_{mn}$ the all-ones $m\times n$-matrix.

Since $A(G)$ and $L(G)$ are symmetric matrices, their eigenvalues are real
numbers. It is easy to see that each row sum of $L(G)$ is equal to zero and
that $L(G)$ is a symmetric positive semi-definite matrix [2, 15]. Therefore
all eigenvalues $\lambda_{i}(G)$ of $L(G)$ are real non-negative numbers and
one of them is equal to zero; we order them in the descendant order:

$\lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G)=0.$

The set $Sp(G)=\\{\lambda_{1}(G),\ldots,\lambda_{n}(G)\\}$ is called the
Laplacian spectrum of $G$.
Some graph properties of the transformations $G^{xyz}$ with
$x,y,z\in\\{+,-\\}$ have been discussed and obtained in [17, 23, 24].
For a regular graph $G$, the adjacency characteristic polynomials and the
adjacency spectrum of $G^{00+}$, $G^{+0+}$, $G^{0++}$ and the total graph
$G^{+++}$ are given in [2] (pages 63 and 64). The adjacency characteristic
polynomials and the adjacency spectrum of the other seven $G^{xyz}$ with
$x,y,z\in\\{+,-\\}$ are obtained in [26]. The definition of
$xyz$-transformation can be easily extended to digraphs, which is also a
generalization of the digraph transformations defined by Liu and Meng [18].
Zhang, Lin, and Meng have described the adjacency characteristic polynomials
of $D^{00+},D^{+0+},D^{0++}$ and the total digraph $D^{+++}$ for any digraph
$D$ [27]. The adjacency characteristic polynomials of other $D^{xyz}$ of a
regular digraph $D$ with $x,y,z\in\\{+,-\\}$ are obtained in [18].
Very few results are known for the Laplacian spectra of transformations. In
1967 A. Kelmans published the following results on the Laplacian polynomial of
$G^{0++}$, $G^{0+0}$, $G^{00+}$, and $G^{l}$ for a regular graph $G$. These
results are included in the survey papers [20] (Theorem 3.8) and [21] (Theorem
1.4.2) with an error, namely, graph $G^{0++}$ is mistakenly called the total
graph of $G$.

######  Theorem 2.2.

[15] Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{0++})=(\lambda-r-1)^{n}(\lambda-2r-2)^{m-n}L(\frac{\lambda^{2}-(r+2)\lambda}{\lambda-r-1},G).$

######  Theorem 2.3.

[15] Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{l})=(\lambda-2r)^{m-n}L(\lambda,G)~{}~{}and~{}~{}L({\lambda,G^{0+0}})=\lambda^{n}L(\lambda,G^{l}).$

######  Theorem 2.4.

[15] Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{00+})=(-1)^{n}(\lambda-2)^{m-n}L(\lambda(r+2-\lambda),G).$

Since $nt(G)=(-1)^{n-1}\lambda^{-1}L(\lambda,G)|_{\lambda=0}$, where $n=v(G)$
[16], we have from Theorems 2.2, 2.3, and 2.4:

######  Theorem 2.5.

[15] Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$t(G^{0++})=\frac{n}{m+n}2^{m-n}(r+1)^{m-1}(r+2)t(G),$
$t(G^{00+})=\frac{n}{m+n}2^{m-n}(r+2)t(G),$

and

$t(G^{l})=\frac{n}{m}2^{m-n}r^{m-n}t(G).$

A set ${\cal A}$ of graphs is closed under complementarity if for every graph
in ${\cal A}$ its complement is also in ${\cal A}$. Given a graph $G$ and
$S\subseteq\\{0,1,+,-\\}$, let ${\cal F}(G,S)$ denote the set of graphs
$G^{xyz}$ such that $x,y,z\in S$. If ${\cal F}(G,S)$ is closed under
complementarity, then in order to find the Laplacian polynomial for the graphs
in ${\cal F}(G,S)$, it is sufficient to find the solutions for a “half” of
graphs in ${\cal F}(G,S)$ and to obtain the solutions for the graphs of the
other “half” using the Reciprocity Theorem 2.6 [16]. It is easy to see that
${\cal F}(G,\\{+,-\\})$ and ${\cal F}(G,\\{0,1,+,-\\})$ (and therefore ${\cal
F}(G,\\{0,1,+,-\\}\setminus\\{+,-\\})$) are closed under complementarity.
Hence the Reciprocity Theorem below can be used for these classes of
transformations.

######  Theorem 2.6.

[16] Let $G$ be a simple graph with $n$ vertices. Then
$(a1)$ $\lambda_{i}(G)+\lambda_{n-i}(G^{c})=n$ for every
$i\in\\{1,\ldots,n-1\\}$ or, equivalently,
$(a2)$ $(n-\lambda)L(\lambda,G^{c})=(-1)^{n-1}\lambda L(n-\lambda,G)$.

Moreover, the matrices $L(G)$ and $L(G^{c})$ are simultaneously
diagonalizable.

Similar results for weighted graphs are obtained in [14].
We will also use the following two classical and simple facts on matrices.

######  Lemma 2.7.

[6, 8] Let $A$ and $D$ be square matrices. Then

$\left|\begin{array}[]{cc}A&\quad B\\\ C&\quad
D\end{array}\right|\quad=\left\\{\begin{array}[]{ll}|A|~{}|D-CA^{-1}B|,&\quad\,\,if\,$A$\mbox{\,
is\, invertible},\\\\[4.30554pt] |D|~{}|A-BD^{-1}C|,&\quad\,\,if\,$D$\mbox{\,
is\, invertible}.\end{array}\right.$

The following two useful and very well known lemmas are obvious.

######  Lemma 2.8.

Given a graph $G$ with $m$ edges, let $G^{l}$ be the line graph of $G$ and $Q$
the incidence matrix of $G$. Then
$(a1)$ $QQ^{\top}=D(G)+A(G)$ and
$(a2)$ $Q^{\top}Q=2I_{m}+A(G^{l})$.

######  Lemma 2.9.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges and let $A$
and $Q$ be the adjacency and the incidence matrix of $G$, respectively. Let
$k$ be a positive integer. Then
$(a1)$ $Q^{\top}J_{nk}=2J_{mk}$,
$(a2)$ $QJ_{mk}=rJ_{nk}$,
$(a3)$ $J_{km}Q^{\top}=rJ_{kn}$,
$(a4)$ $J_{kn}Q=2J_{km}$,
$(a5)$ $J_{kn}A=rJ_{kn}$, and
$(a6)$ $AJ_{nk}=rJ_{nk}$.

######  Lemma 2.10.

Let $G$ be an $r$-regular graph with $n$ vertices, $A(G)=A$, and
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}=0$ the list of the
Laplacian eigenvalues of $G$. Let $P(x,y)$ be a polynomial with two variables
and real coefficients. Then matrix $P(A,J_{nn})$ has the eigenvalues
$\sigma_{n}=P(r,n)$ and $\sigma_{i}=P(r-\lambda_{i},0)$ for
$i=1,2,\cdots,n-1.$

Proof. Since the Laplacian matrix $L=L(G)$ is symmetric and real, there is a
list $B=\\{X_{1},X_{2},\cdots,X_{n}\\}$ of mutually orthogonal eigenvectors of
$L$, where $X_{i}$ corresponds to $\lambda_{i}$ and $X_{n}=J_{n1}$. Since
$A=rI_{n}-L$, clearly $AX_{i}=(r-\lambda_{i})X_{i}$ for each $i$. Since $B$ is
an orthogonal basis, $J_{nn}X_{i}=0$ for each $i\neq n$. Clearly,
$J_{nn}J_{n1}=nJ_{n1}$ and $J_{nn}^{2}=nJ_{nn}$. By Lemma 2.9,
$AJ_{nn}=J_{nn}A=rJ_{nn}$. Therefore, $P(A,J_{nn})~{}X_{n}=P(r,n)~{}X_{n}$ and
$P(A,J_{nn})~{}X_{i}=P(r-\lambda_{i},0)~{}X_{i}$ for each $i\neq n$. $\square$
The arguments in this proof are similar to those in [14].

##  3 Laplacian spectra of $G^{xyz}$ with
$\\{x,y,z\\}\cap\\{0,1\\}\neq\emptyset$

Given a graph $G$ with $n$ vertices and $m$ edges, we always denote by $A$,
$D$ and $Q$, the adjacency matrix, the degree matrix and the incidence matrix
of $G$, respectively, and so if $G$ is an $r$-regular graph, then $D=rI_{n}$
and $2m=rn$. We put $\lambda_{i}(G)=\lambda_{i}$, and so
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}=0$ is the list of the
Laplacian eigenvalues of $G$.

###  3.1 Laplacian spectra of $G^{xyz}$ with $z=0$

We start with the following simple observation.

######  Theorem 3.1.

Let $G$ be a graph with $n$ vertices and $m$ edges and let
$x,y\in\\{0,1,+,-\\}$. Then
$L(\lambda,G^{xy0})=L(\lambda,G^{x})L(\lambda,(G^{l})^{y})$.

Since $L(\lambda,G^{0})=\lambda^{n}$, $L(\lambda,G^{+})=L(\lambda,G)$ and
$L(\lambda,G^{1})=\lambda(\lambda-n)^{n-1}$, we can calculate
$L(\lambda,G^{xy0})$ for $x,y\in\\{0,1,+,-\\}$ from Theorems 2.3, 2.6 and 3.1.

######  Theorem 3.2.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then
$(a1)$ $L(\lambda,G^{x00})=\lambda^{m}L(\lambda,G^{x})$ and
$L(\lambda,G^{x10})=\lambda(\lambda-m)^{m-1}L(\lambda,G^{x})$ for
$x\in\\{0,1,+\\}$,
$(a2)$
$L(\lambda,G^{-00})=(-1)^{n}(\lambda-n)^{-1}\lambda^{m+1}L(n-\lambda,G)$,
$(a3)$
$L(\lambda,G^{-10})=(-1)^{n}\lambda^{2}(\lambda-n)^{-1}(\lambda-m)^{m-1}L(n-\lambda,G)$,
$(a4)$
$L(\lambda,G^{0-0})=(-1)^{n}(\lambda-m)^{-1}\lambda^{n+1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)$,

$L(\lambda,G^{1-0})=(-1)^{n}(\lambda-m)^{-1}\lambda^{2}(\lambda-n)^{n-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)$,
$(a5)$ $L(\lambda,G^{++0})=(\lambda-2r)^{m-n}L(\lambda,G)^{2}$,

$L(\lambda,G^{-+0})=(-1)^{n}(\lambda-2r)^{m-n}\lambda(\lambda-n)^{-1}L(n-\lambda,G)L(\lambda,G)$,
$(a6)$ $L({\lambda,G^{0+0}})=\lambda^{n}(\lambda-2r)^{m-n}L(\lambda,G)$,

$L(\lambda,G^{1+0})=\lambda(\lambda-n)^{n-1}(\lambda-2r)^{m-n}L(\lambda,G)$,
$(a7)$
$L(\lambda,G^{+-0})=(-1)^{n}\lambda(\lambda-m)^{-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)L(\lambda,G)$
and

$L(\lambda,G^{--0})=\lambda^{2}(\lambda-m)^{-1}(\lambda-n)^{-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)L(n-\lambda,G)$.

###  3.2 Laplacian spectra of $G^{xyz}$ for $z=+$ and $x,y\in\\{0,1\\}$

######  Theorem 3.3.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{00+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{\lambda^{2}-\lambda(r+2)+\lambda_{i}\\}$

or equivalently,

$L(\lambda,G^{00+})=(-1)^{n}(\lambda-2)^{m-n}L(\lambda(r+2-\lambda)),G).$

Proof. It is easy to see that

$A(G^{00+})=\left(\begin{array}[]{cc}0&\quad Q\\\\[4.30554pt] Q^{\top}&\quad
0\end{array}\right)\hbox{\ and\
}D(G^{00+})=\left(\begin{array}[]{cc}rI_{n}&\quad 0\\\ 0&\quad
2I_{m}\end{array}\right).$

We know that $L(G^{00+})=D(G^{00+})-A(G^{00+})$ and
$L(\lambda,G^{00+})=\det(\lambda I_{n}-L(G^{00+}))$. Therefore

$\displaystyle L(\lambda,G^{00+})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-r)I_{n}&\quad Q\\\\[4.30554pt]
Q^{\top}&\quad(\lambda-2)I_{m}\end{array}\right|.$

Clearly, it is sufficient to prove our claim for $\lambda\neq 2$. Now using
Lemmas 2.7 we obtain:

$L(\lambda,G^{00+})=|(\lambda-2)I_{m}|\times|(\lambda-r)I_{n}-\frac{1}{\lambda-2}QI_{m}Q^{\top}|.$

By Lemma 2.8 $(a1)$, $QQ^{\top}=rI_{n}+A$. Therefore
$L(\lambda,G^{00+})=(\lambda-2)^{m-n}\times|B|$, where
$B=(\lambda-2)(\lambda-r)I_{n}-(rI_{n}+A).$
Obviously, $|B|$ equals the product of its eigenvalues. By Lemma 2.10, the
eigenvalues of $B$ are
$\sigma_{n}=(\lambda-2)((\lambda-r))-(r+r)=\lambda(\lambda-r-2)$ and
$\sigma_{i}=(\lambda-2)(\lambda-r)-(r+r-\lambda_{i})=\lambda^{2}-(r+2)\lambda+\lambda_{i}$
for $i=1,2,\ldots,n-1$.
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$, we have:
$L(\lambda,G^{00+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{\lambda^{2}-(r+2)\lambda+\lambda_{i}\\}.$
$\square$

######  Corollary 3.4.

If $G$ is an $r$-regular graph with $n$ vertices and $m$ edges, then $G^{00+}$
has $m-n$ Laplacian eigenvalues equal to $2$ and the following $2n$ Laplacian
eigenvalues

$\frac{1}{2}(~{}r+2\pm\sqrt{(r+2)^{2}-4\lambda_{i}}~{}),\ i=1,2,\cdots,n.$

######  Corollary 3.5.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$t(G^{00+})=\frac{n}{m+n}(r+2)2^{m-n}t(G).$

Similarly, we can prove the following theorem.

######  Theorem 3.6.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then
$(a1)$
$L(\lambda,G^{10+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-
n-r)-2r+\lambda_{i}\\}$,
$(a2)$
$L(\lambda,G^{01+})=\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-m-2)-2r+\lambda_{i}\\}$
and
$(a3)$
$L(\lambda,G^{11+})=\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r)(\lambda-m-2)-2r+\lambda_{i}\\}.$

###  3.3  Laplacian spectra of $G^{xyz}$ for $z=+$ and
$|\\{x,y\\}\cap\\{0,1\\}|=1$

######  Theorem 3.7.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{+0+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-r-\lambda_{i})-2r+\lambda_{i}\\}$

or equivalently,

$L(\lambda,G^{+0+})=(\lambda-2)^{m-n}(\lambda-3)^{n}L(\frac{\lambda^{2}-\lambda(r+2)}{\lambda-3},G).$

Proof. The adjacency matrix and the degree matrix of $G^{+0+}$ are

$A(G^{+0+})=\left(\begin{array}[]{cc}A&\quad Q\\\\[4.30554pt] Q^{\top}&\quad
0\end{array}\right)\hbox{\ and \
}D(G^{+0+})=\left(\begin{array}[]{cc}2rI_{n}&\quad 0\\\\[4.30554pt] 0&\quad
2I_{m}\end{array}\right).$

Therefore

$\displaystyle L(\lambda,G^{+0+})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-2r)I_{n}+A&\quad
Q\\\\[5.59721pt] Q^{\top}&\quad(\lambda-2)I_{m}\end{array}\right|.$

Clearly, it is sufficient to prove our claim for $\lambda\neq 2$. Now using
Lemmas 2.7 we obtain:

$L(\lambda,G^{+0+})=(\lambda-2)^{m}|(\lambda-2r)I_{n}+A-\frac{1}{\lambda-2}QQ^{\top}|.$

By Lemma 2.8 $(a1)$, $QQ^{\top}=rI_{n}+A$. Therefore
$L(\lambda,G^{+0+})=(\lambda-2)^{m-n}~{}{B}$, where
$B=(\lambda-2)(\lambda-2r)I_{n}+(\lambda-2)A-(rI_{n}+A).$
Obviously, $|B|$ equals the product of its eigenvalues. By Lemma 2.10, the
eigenvalues of $B$ are
$\sigma_{n}=(\lambda-2)(\lambda-2r)+(\lambda-2)r-(r+r)=\lambda(\lambda-r-2)$
and
$\sigma_{i}=(\lambda-2)(\lambda-r-\lambda_{i})-2r+\lambda_{i}$ for
$i=1,2\ldots,n-1$.
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$, we have:
$L(\lambda,G^{+0+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-r-\lambda_{i})-2r+\lambda_{i}\\}.$
$\square$

######  Corollary 3.8.

If $G$ is an $r$-regular graph with $n$ vertices and $m$ edges, then $G^{+0+}$
has $m-n$ Laplacian eigenvalues equal to $2$ and the following $2n$ Laplacian
eigenvalues

$\frac{1}{2}(~{}r+2+\lambda_{i}\pm\sqrt{(r+2+\lambda_{i})^{2}-12\lambda_{i}}~{}),\
i=1,2,\cdots,n.$

######  Corollary 3.9.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$t(G^{+0+})=\frac{n}{m+n}(r+2)2^{m-n}3^{n-1}t(G),$

and so

$t(G^{+0+})=3^{n-1}t(G^{00+}).$

######  Theorem 3.10.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{0++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$

or equivalently,

$L(\lambda,G^{0++})=(\lambda-r-1)^{n}(\lambda-2r-2)^{m-n}L(\frac{\lambda^{2}-(r+2)\lambda}{\lambda-r-1},G).$

Proof. The adjacency matrix and the degree matrix of $G^{0++}$ are

$A(G^{0++})=\left(\begin{array}[]{cc}0&\quad Q\\\\[4.30554pt] Q^{\top}&\quad
A(G^{l})\end{array}\right)\hbox{\ and \
}D(G^{0++})=\left(\begin{array}[]{cc}rI_{n}&\quad 0\\\\[4.30554pt] 0&\quad
2rI_{m}\end{array}\right).$

Since by Lemma 2.8 $(a2)$, $A(G^{l})=Q^{\top}Q-2I_{m}$, we have:

$\displaystyle L(\lambda,G^{0++})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-r)I_{n}&~{}~{}\quad
Q\\\\[6.45831pt]
Q^{\top}&~{}~{}\quad(\lambda-2r-2)I_{m}+Q^{\top}Q\end{array}\right|$
$\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-r)I_{n}&~{}~{}\quad
Q\\\\[6.45831pt]
(r+1-\lambda)Q^{\top}&~{}~{}\quad(\lambda-2r-2)I_{m}\end{array}\right|.$

Clearly, it is sufficient to prove our claim for $\lambda\neq 2r+2$. Using
Lemmas 2.7 we obtain:

$\displaystyle L(\lambda,G^{0++})$ $\displaystyle=$
$\displaystyle(\lambda-2r-2)^{m}|(\lambda-r)I_{n}-\frac{r+1-\lambda}{\lambda-2r-2}QQ^{\top}|.$

By Lemma 2.8 $(a1)$, $QQ^{\top}=rI_{n}+A$. Therefore
$L(\lambda,G^{0++})=(\lambda-2r-2)^{m-n}~{}|B|$, where
$B=(\lambda-r)(\lambda-2r-2)I_{n}-(r+1-\lambda)(rI_{n}+A)$.
Obviously, $|B|$ equals the product of its eigenvalues. By Lemma 2.10, the
eigenvalues of $B$ are
$\sigma_{n}=(\lambda-r)(\lambda-2r-2)-(r+1-\lambda)(r+r)=\lambda(\lambda-r-2)$
and
$\sigma_{i}=(\lambda-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}$ for
$i=1,2,\ldots,n-1$.
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$, we have:
$L(\lambda,G^{0++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$.
$\square$

######  Corollary 3.11.

If $G$ is an $r$-regular graph with $n$ vertices and $m$ edges, then $G^{0++}$
has $m-n$ Laplacian eigenvalues equal to $2r+2$ and the following $2n$
Laplacian eigenvalues

$\frac{1}{2}(~{}r+2+\lambda_{i}\pm\sqrt{\lambda_{i}^{2}-2r\lambda_{i}+r^{2}+4r+4}~{}),~{}~{}i=1,2,\cdots,n.$

######  Corollary 3.12.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$t(G^{0++})=\frac{n}{m+n}2^{m-n}(r+1)^{m-1}(r+2)t(G).$

Theorems 3.3 and 3.10 and Corollaries 3.5, 3.9, and 3.12 coincide with the
corresponding Theorems 2.2, 2.4, and 2.5 by Kelmans.
The remaining situations when $z=+$ and $|\\{x,y\\}\cap\\{0,1\\}|=1$ can be
considered similarly. Here is the list of the Laplacian characteristic
polynomials of $G^{xyz}$ for these situations.

######  Theorem 3.13.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then
$L(\lambda,G^{0-+})=\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-m-2-\lambda_{i})-2r+\lambda_{i}\\},$
$L(\lambda,G^{-0+})=\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-2)-2r+\lambda_{i}\\},$
$L(\lambda,G^{1-+})=\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r)(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\},$
$L(\lambda,G^{-1+})=\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-m-2)-2r+\lambda_{i}\\},$
$L(\lambda,G^{+1+})=\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-m-2)-2r+\lambda_{i}\\}$
and
$L(\lambda,G^{1++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}.$

###  3.4  Laplacian spectra of $G^{xyz}$ for $z\in\\{1,-\\}$

Using the Reciprocity Theorem 2.6 it is easy to find from Theorems 3.2, 3.3,
3.6, 3.7, 3.10 and 3.13 the Laplacian characteristic polynomial of every
$G^{xyz}$ with $\\{x,y\\}\cap\\{0,1\\}\neq\emptyset$ and $z\in\\{1,-\\}$ (see
Appendix).

##  4 Laplacian spectra of $G^{xyz}$ with $x,y,z\in\\{+,-\\}$

In this section we will describe the Laplacian characteristic polynomials and
the Laplacian spectra of transformations $G^{xyz}$ of an $r$-regular graph $G$
for $x,y,z\in\\{+,-\\}$ in terms of the Laplacian spectrum of $G$, $r$,
$v(G)=n$, $r$ (and $e(G)=m=\frac{1}{2}rn$).

######  Theorem 4.1.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{+++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}.$

Proof. The adjacency matrix and the degree matrix of $G^{+++}$ are

$A(G^{+++})=\left(\begin{array}[]{cc}A&\quad Q\\\\[4.30554pt] Q^{\top}&\quad
A(G^{l})\end{array}\right)~{}~{}\hbox{\ and\
}~{}~{}D(G^{+++})=\left(\begin{array}[]{cc}2rI_{n}&\quad 0\\\\[4.30554pt]
0&\quad 2rI_{m}\end{array}\right).$

Since $L(G^{+++})=D(G^{+++})-A(G^{+++})$, $L(\lambda,G^{+++})=\det(\lambda
I_{n}-L(G^{+++}))$, and by Lemma 2.8 $(a2)$, $A(G^{l})=Q^{\top}Q-2I_{m}$, we
have:

$\displaystyle L(\lambda,G^{+++})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-2r)I_{n}+A&~{}~{}\quad
Q\\\\[10.76385pt]
Q^{\top}&~{}~{}\quad(\lambda-2r-2)I_{m}+Q^{\top}Q\end{array}\right|$
$\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-2r)I_{n}+A&~{}~{}\quad
Q\\\\[10.76385pt]
-Q^{\top}((\lambda-2r-1)I_{n}+A)&~{}~{}\quad(\lambda-2r-2)I_{m}\end{array}\right|.$

Clearly, it is sufficient to prove our claim for $\lambda\neq 2r+2$. Using
Lemmas 2.7 we obtain:

$L(\lambda,G^{+++})=|(\lambda-2r-2)I_{m}|\times|(\lambda-2r)I_{n}+A+(\lambda-2r-2)^{-1}QQ^{\top}((\lambda-2r-1)I_{n}+A)|.$

By Lemma 2.8 $(a1)$, $QQ^{\top}=rI_{n}+A$. Therefore
$L(\lambda,G^{+++})=(\lambda-2r-2)^{m-n}\times|B|$, where

$B=|(\lambda-2r-2)((\lambda-2r)I_{n}+A)+(rI_{n}+A)((\lambda-2r-1)I_{n}+A)|.$

Obviously, $|B|$ equals the product of its eigenvalues. By Lemma 2.10, the
eigenvalues of $B$ are
$\sigma_{i}=(\lambda-2r-2)((\lambda-2r)+r-\lambda_{i})+(r+r-\lambda_{i})((\lambda-2r-1)+r-\lambda_{i})\\\
~{}~{}~{}~{}=(\lambda-r-\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}$
for $i=1,2,\ldots,n$.
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$ and $\lambda_{n}=0$, we have:
$L(\lambda,G^{+++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}.$
$\square$

######  Theorem 4.2.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{+-+})=\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}.$

Proof. From the definition of $G^{+-+}$, we have:

$A(G^{+-+})=\left(\begin{array}[]{cc}A&~{}~{}Q\\\\[6.45831pt]
Q^{\top}&~{}~{}J_{mm}-I_{m}-A(G^{l})\\\ \end{array}\right).$

For every $z\in V(G^{+-+})$, $d(z,G^{+-+})=2r$ if $z\in V(G)$ and
$d(z,G^{+-+})=2+m-1-(2r-2)=m-2r+3$ if $z\in E(G)$. Therefore,

$D(G^{+-+})=\left(\begin{array}[]{cc}2rI_{n}&~{}~{}0\\\\[6.45831pt]
0&~{}~{}(m-2r+3)I_{m}\\\ \end{array}\right).$

Then $L(\lambda,G^{+-+})=|M|$, where

$\displaystyle M$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}(\lambda-2r)I_{n}+A&~{}~{}~{}Q\\\\[8.61108pt]
Q^{\top}&~{}~{}~{}~{}(\lambda-m+2r-2)I_{m}+J_{mm}-Q^{\top}Q\\\
\end{array}\right).$

By Lemma 2.9 $(a4)$, $J_{mn}Q=2J_{mm}$. Hence multiplying the first row of the
block matrix $M$ by $Q^{\top}-\frac{1}{2}J_{mn}$ and adding the result to the
second row of $M$, we obtain a new matrix

$\displaystyle M^{\prime}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}(\lambda-2r)I_{n}+A&~{}~{}~{}~{}Q\\\\[8.61108pt]
Q^{\top}((\lambda-2r+1)I_{n}+A)-\frac{1}{2}J_{mn}((\lambda-2r)I_{n}+A)&~{}~{}~{}~{}(\lambda-m+2r-2)I_{m}\\\
\end{array}\right).$

Clearly, $L(\lambda,G^{+-+})=|M|=|M^{\prime}|$. Obviously, it is sufficient to
prove our claim for $\lambda\neq m-2r+2$. Now using Lemmas 2.7 we obtain:
$L(\lambda,G^{+-+})=(\lambda-m+2r-2)^{m-n}\times|B|$, where
$B=(\lambda-m+2r-2)((\lambda-2r)I_{n}+A)-QQ^{\top}((\lambda-2r+1)I_{n}+A)+\frac{1}{2}QJ_{mn}((\lambda-2r)I_{n}+A)$.
By Lemma 2.8 $(a1)$, $QQ^{\top}=rI_{n}+A$ and by Lemma 2.9 $(a2)$,
$QJ_{mn}=rJ_{nn}$. Therefore
$B=(\lambda-m+2r-2)((\lambda-2r)I_{n}+A)-(rI_{n}+A)((\lambda-2r+1)I_{n}+A)+\frac{r}{2}J_{nn}((\lambda-2r)+A).$
Obviously, $|B|$ equals the product of its eigenvalues and $nr=2m$. By Lemma
2.10, the eigenvalues of $B$ are
$\sigma_{n}=(\lambda-m+2r-2)(\lambda-2r+r)-2r(\lambda-2r+1+r)+\frac{nr}{2}(\lambda-2r+r)=\lambda^{2}-\lambda(r+2)$
and
$\sigma_{i}=(\lambda-m+2r-2)(\lambda-2r+r-\lambda_{i})-(2r-\lambda_{i})(\lambda-2r+r+1-\lambda_{i})\\\
~{}~{}~{}~{}=(\lambda-r-\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}$
for $i=1,2,\cdots,n-1.$
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$, we have:
$L(\lambda,G^{+-+})=\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}.$

$\square$

######  Theorem 4.3.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{-++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}.$

Proof. From the definition of $G^{-++}$ we have:

$A(G^{-++})=\left(\begin{array}[]{cc}J_{nn}-I_{n}-A&\quad Q\\\ Q^{\top}&\quad
A(G^{l})\end{array}\right).$

For every vertex $z$ in $G^{-++}$, we have: $d(z,G^{-++})=n-1$ if $z\in V(G)$
and $d(z,G^{-++})=2r$ if $z\in E(G)$, and so

$D(G^{-++})=\left(\begin{array}[]{cc}(n-1)I_{n}&\quad 0\\\ 0&\quad
2rI_{m}\end{array}\right).$

By Lemma 2.8 $(a2)$, $A(G^{l})=2I_{m}-Q^{\top}Q$. Therefore

$\displaystyle L(\lambda,G^{-++})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-n+1)I_{n}+J_{nn}-I_{n}-A&Q\\\\[6.45831pt]
Q^{\top}&~{}~{}(\lambda-2r)I_{m}+Q^{\top}Q-2I_{m}\\\ \end{array}\right|.$

Multiplying the first row of the above block matrix by $-Q^{\top}$ and adding
the result to the second row we obtain:

$\displaystyle L(\lambda,G^{-++})$ $\displaystyle=$
$\displaystyle\left|\begin{array}[]{cc}(\lambda-n)I_{n}+J_{nn}-A&~{}~{}Q\\\\[6.45831pt]
Q^{\top}-Q^{\top}((\lambda-n)I_{n}+J_{nn}-A)&~{}~{}(\lambda-2r-2)I_{m}\\\
\end{array}\right|.$

Clearly, it is sufficient to prove our claim for $\lambda\neq 2r+2$. Using
Lemmas 2.7 we obtain:

$\begin{array}[]{rl}L(\lambda,G^{-++})=&(\lambda-2r-2)^{m-n}\times|B|,\end{array}$

where

$\begin{array}[]{rl}B=&(\lambda-2r-2)((\lambda-n)I_{n}+J_{nn}-A)-QQ^{\top}((1-\lambda+n)I_{n}-J_{nn}+A).\end{array}$

Since by Lemma 2.8 $(a1)$, $QQ^{\top}=D(G)+A(G)=rI_{n}+A$, we have:

$\begin{array}[]{rl}B=&(\lambda-2r-2)((\lambda-n)I_{n}+J_{nn}-A)-(rI_{n}+A)((1-\lambda+n)I_{n}-J_{nn}+A).\end{array}$

Obviously, $|B|$ is the product of the eigenvalues of $B$. By Lemma 2.10, the
eigenvalues of $B$ are
$\sigma_{n}=(\lambda-2r-2)(\lambda-n+n-r)-(r+r)(1-\lambda+n-n+r)=\lambda(\lambda-r-2)$
and
$\sigma_{i}=(\lambda-2r-2)(\lambda-
n-r+\lambda_{i})-(r+r-\lambda_{i})((1-\lambda+n)+r-\lambda_{i})\\\
~{}~{}~{}~{}=(\lambda-2-\lambda_{i})(\lambda-n-r+\lambda_{i})-2r+\lambda_{i}$
for $i=1,2,\ldots,n-1$.
Since $|B|=\prod_{i=1}^{n}\sigma_{i}$, we have:
$L(\lambda,G^{-++})=\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}.$

$\square$

Similarly we can prove the following theorem for $G^{--+}$:

######  Theorem 4.4.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. Then

$L(\lambda,G^{--+})=\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}.$

Now we can use Reciprocity Theorem 2.6 to obtain from Theorems 4.1 \- 4.4 the
Laplacian characteristic polynomials of the corresponding complement graphs
$G^{xyz}$.

######  Theorem 4.5.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges and let
$s=n+m$. Then
$(a1)$
$L(\lambda,G^{---})=\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}\times\\\
\indent~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\},$
$(a2)$
$L(\lambda,G^{-+-})=\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}\times\\\
\indent~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\},$
$(a3)$
$L(\lambda,G^{+--})=\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}\times\\\
\indent~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\prod_{i=1}^{n-1}\\{(\lambda-m+r-\lambda_{i})(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\},$
and
$(a4)$
$L(\lambda,G^{++-})=\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}\times\\\
\indent~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\prod_{i=1}^{n-1}\\{(\lambda-m+r-\lambda_{i})(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\}.$

Proof. As we have mentioned above, the claims $(a1)$ \- $(a4)$ can be easily
proven from Theorems 4.1 \- 4.4, respectively, using Reciprocity Theorem 2.6.
We give below the proof of claim $(a1)$. The proofs of the remaining claims
$(a2)$ \- $(a4)$ are similar.
Since $G^{+++}$ and $G^{---}$ are complement, we can apply Reciprocity Theorem
to obtain from Theorem 4.1:
$L(\lambda,G^{---})=(-1)^{s-1}\frac{\lambda}{s-\lambda}L(s-\lambda,G^{+++})$
$=(-1)^{s-1}\frac{\lambda}{s-\lambda}(s-\lambda)(s-\lambda-r-2)(s-\lambda-2r-2)^{m-n}\prod_{i=1}^{n-1}\\{(s-\lambda-r-\lambda_{i})(s-\lambda-2\lambda_{i})-2r+\lambda_{i}\\}$
$=\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\}.$
$\square$
From the above results it follows that the transformations $G^{xyz}$ have the
following common Laplacian spectrum properties.

######  Theorem 4.6.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges and
$F=G^{xyz}$, where $z\in\\{+,-\\}$. Then $F$ and $F^{c}$ have, respectively,
the Laplacian eigenvalue
$(a1)$ $r+2$ and $m+n-r-2$ of multiplicity one if $z=+$,
$(a2)$ $2r+2$ and $m+n-2r-2$ of multiplicity $m-n$ if $(y,z)=(+,+)$,
$(a3)$ $m-2r+2$ and $n+2r-2$ of multiplicity $m-n$ if $(y,z)=(-,+)$,
$(a4)$ $2$ and $m+n-2$ of multiplicity $m-n$ if $(y,z)=(0,+)$, and
$(a5)$ $m+2$ and $n-2$ of multiplicity $m-n$ if $(y,z)=(1,+)$.

The proofs of Theorems 3.6$(a1)$, 3.6$(a2)$, and 4.4 can be found in
[DKMarxiv].

##  5 Transformation graphs of cycles

In this section we first describe some $xyz$-transformations of the 4-cycle
and the 5-cycle and the Laplacian spectra of these transformations. After that
we consider $xyz$-transformations of any cycle and show that some different
$xyz$-transformations of the same cycle may be isomorphic.

Figure 2: The 4-cycle $C_{4}$ and its transformations $C_{4}^{+++}$ (middle)
and $C_{4}^{++-}$ (right)

Figure 3:  $C_{4}^{--+}$ (left) and $C_{4}^{---}$ (right)

Figure 4: $C_{4}^{-++}$ (left) and $C_{4}^{+-+}$ (right)

Let $C_{n}$ be the cycle with $n$ vertices. It is known (see, for example,
[2]) that
$Sp(C_{n})=\\{2-2~{}cos~{}\frac{2\pi}{n}i:i=1,\ldots,n\\}$.
Let $G$ be a 4-cycle $C_{4}$. It is easy to see (and it follows from the above
formula for $C_{n}$) that $Sp(C_{4})=\\{4,2^{(2)},0\\}$. Then
${\bf(c1)}$ $C_{4}^{+++}$ and $C_{4}^{++-}$ are isomorphic and by Theorem 4.1
or 4.5
$Sp(C_{4}^{+++})=Sp(C_{4}^{++-})=\\{6^{(2)},[4+\sqrt{2}]^{(2)},4,[4-\sqrt{2}]^{(2)},0\\}$,
${\bf(c2)}$ $C_{4}^{--+}$ and $C_{4}^{---}$ are isomorphic and by Theorem 4.4
or 4.5,
$Sp(C_{4}^{--+})==Sp(C_{4}^{---})=\\{[4+\sqrt{2}]^{(2)},4,[4-\sqrt{2}]^{(2)},2^{(2)},0\\}$,
and
${\bf(c3)}$ $C_{4}^{-++}$ and $C_{4}^{+-+}$ are isomorphic and by Theorem 4.2
or 4.3,
$Sp(C_{4}^{-++})=Sp(C_{4}^{+-+})=\\{6,[4+\sqrt{2}]^{(2)},4,[4-\sqrt{2}]^{(2)},2,0\\}$.

Figure 5: The 5-cycle $C_{5}$ and its transformation $C_{5}^{+++}$

Figure 6:  $C_{5}^{--+}$

Figure 7: $C_{5}^{-++}$ (left) and $C_{5}^{+-+}$ (right)

It is easy to prove that $B(C_{4})$ and $B^{c}(C_{4})$ are isomorphic.
Therefore $C_{4}^{xy+}$ and $C_{4}^{xy-}$ are isomorphic for any
$x,y\in\\{0,1,+,-\\}$.
It is also interesting to consider some transformations of the 5-cycle $C_{5}$
(the pentagon) because $C_{5}$ is isomorphic to its complement and $C_{5}$ is
also isomorphic to its line graph. By the above formula for $C_{n}$, we have:
$Sp(C_{5})=\\{[\frac{1}{2}(5+\sqrt{5})]^{(2)},~{}[\frac{1}{2}(5-\sqrt{5})]^{(2)},~{}0\\}$.
Then
${\bf(p1)}$ $C_{5}^{+++}$ is a 4-regular graph (see Fig. 5) and by Theorem
4.1,
$Sp(C_{5}^{+++})=\\{[\frac{1}{2}\langle
9+\sqrt{5}+\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
9+\sqrt{5}-\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}4,~{}\\\
\indent[\frac{1}{2}\langle
9-\sqrt{5}+\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
9-\sqrt{5}-\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}0\\}$,
${\bf(p2)}$ $C_{5}^{--+}$ is a 4-regular graph (see Fig. 6) and by Theorem
4.4,
$Sp(C_{5}^{--+})=\\{[\frac{1}{2}\langle
13+\sqrt{5}+\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
13+\sqrt{5}-\sqrt{6-2\sqrt{5}}\rangle]^{(2)},~{}\\\ \indent[\frac{1}{2}\langle
13-\sqrt{5}+\sqrt{6+2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
13-\sqrt{5}-\sqrt{6+2\sqrt{5}}\rangle]^{(2)},~{}4,~{}0\\}$,
${\bf(p3)}$ $C_{5}^{-++}$ and $C_{5}^{+-+}$ are isomorphic 4-regular graphs
(see Fig. 7) and by Theorem 4.2 or 4.3,
$Sp(C_{5}^{-++})=Sp(C_{5}^{+-+})=\\{[\frac{1}{2}\langle
9+\sqrt{11+2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
9+\sqrt{11-2\sqrt{5}}\rangle]^{(2)},~{}\\\ \indent 4,~{}[\frac{1}{2}\langle
9+\sqrt{11-2\sqrt{5}}\rangle]^{(2)},~{}[\frac{1}{2}\langle
9-\sqrt{11+\sqrt{5}}\rangle]^{(2)},~{}0\\}$.
By (c3) and (p3), $G^{-++}$ and $G^{+-+}$ are isomorphic if $G$ is either
$C_{4}$ or $C_{5}$. As we will see below, a more general claim is true not
only for $C_{4}$ and $C_{5}$ but for any cycle $C$.

######  Theorem 5.1.

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges. If $m=n$,
then $G^{xyz}$ and $G^{yxz}$ are isomorphic for all $x,y,z\in\\{0,1,+,-\\}$.

Proof. By the Reciprocity Theorem 2.6, it is sufficient to prove our claim for
$x,y\in\\{0,1,+,-\\}$ and $z\in\\{0,+\\}$. Since $m=n$ and $nr=2m$, we have
$r=2$, and so $G$ is 2-regular. Then $G$ is a disjoint union of cycles. If $A$
and $B$ are disjoint graphs, then $(A\cup B)^{xy0}=A^{xy0}\cup A^{xy0}$ and
$(A\cup B)^{xy+}=A^{xy+}\cup A^{xy+}$. Therefore it is sufficient to prove our
claim for a connected graph $G$. In this case $G$ is a cycle on $n$ vertices
and we can assume that $V(G)=V=\\{v_{1},\cdots,v_{n}\\}$ and
$E(G)=E=\\{e_{i}:i=1,\cdots,n\\}$, where $e_{i}=v_{i}v_{i+1}$ for
$i=1,\cdots,n$ and $i+1$ is considered $\bmod~{}n$, and so $e_{n}=v_{n}v_{1}$.
Let for each $i$, $\alpha(v_{i})=\sigma(v_{i+1})=e_{i}$. Then both $\alpha$
and $\sigma$ are isomorphisms from $G$ to $G^{l}$. Recall that $G^{+}=G$,
$G^{-}=G^{c}$, $G^{0}$ is the the graph with $V(G^{0})=V$ and with no edges ,
and $G^{1}$ the a complete graph with $V(G^{1})=V$. Hence for every
$x\in\\{0,1,+,-\\}$, both $\alpha$ and $\sigma$ are isomorphisms from $G^{x}$
to $(G^{l})^{x}$. Put $\pi|_{V}=\alpha\ \mbox{\ and \ }\
\pi|_{E}=\sigma^{-1}$. Since $G^{xy0}$ is a disjoint union of $G^{x}$ and
$(G^{l})^{y}$, we have: $\pi$ is an isomorphism from $G^{xy0}$ to $G^{yx0}$.

Now we show that $\pi$ is also an isomorphism from $G^{xy+}$ to $G^{yx+}$. By
definition of $G^{xy+}$, $E(G^{xy+})=E(G^{x})\cup E((G^{l})^{y})\cup E(W)$,
where $E(W)=\\{v_{i}e_{i},v_{i+1}e_{i}:i=1,\ldots,n\\}$. Recall that each
$e_{i}=v_{i}v_{i+1}$. Since $\pi(v_{i})=\alpha(v_{i})=e_{i}$ and
$\pi(e_{j})=\sigma^{-1}(e_{j})=v_{j+1}$, vertices $\pi(v_{i})$ and
$\pi(e_{j})$ are adjacent in $G^{yx+}$ if and only if $j+1=i$ or $j+1=i+1$
which is equivalent to $i=j+1$ or $i=j$. Therefore $v_{i}$ and $e_{j}$ are
adjacent in $G^{xy+}$ if and only if $\pi(v_{i})$ and $\pi(e_{j})$ are
adjacent in $G^{yx+}$. $\square$

##  6 Some remarks and questions

${\bf(R1)}$ Each factor of the Laplacian polynomials of $G^{xyz}$
($x,y,z\in\\{0,1,+,-\\}$) is a polynomial in $\lambda$ of degree one or two.
Therefore the explicit formula for the Laplacian spectrum and the number of
spanning trees of $G^{xyz}$ can be given in terms of those of $G$,
respectively, as in Corollaries 3.4, 3.8, and 3.11.
${\bf(R2)}$ Let ${\cal R}$ be the set of regular graphs. Obviously, if
$G\in{\cal R}$, then $G^{c}\in{\cal R}$ and $G^{l}\in{\cal R}$. If $G$ is an
$r$-regular graph, then $G^{+++}$ is $2r$-regular and $G^{---}$ is
$(v(G)+e(G)-2r-1)$-regular, and so if $G\in{\cal R}$, then $G^{+++}\in{\cal
R}$. In other words, the set ${\cal R}$ of regular graphs is closed under
$c$-operation, $l$-operation, $(+++)$-operation, and $(---)$-operation.
Therefore using the corresponding results described above, one can give an
algorithm (and the computer program) that for any series $Z$ of $c$-, $l$-,
$(+++)$-, and $(---)$-operations and the Laplacian spectrum $Sp(G)$ of any
$r$-regular graph $G$ provides the formula of the Laplacian spectrum of graph
$F$ obtained from $G$ by the operation series $Z$ in terms of $r$, $v(G)$, and
$Sp(G)$.
${\bf(R3)}$ Examples and results in Section 5 show that there exists a regular
graph $G$ such that $G^{xyz}$ and $G^{x^{\prime}y^{\prime}z^{\prime}}$ are
isomorphic although $(x,y,z)\neq(x^{\prime},y^{\prime},z^{\prime})$, where
$x,y,z\in\\{0,1,+,-\\}$. It is also easy to see that if $K$ is a complete
graph, then $K^{0yz}=K^{-yz}$ and $K^{x0z}=K^{x-z}$ as well as
$K^{1yz}=K^{+yz}$ and $K^{x1z}=K^{x+z}$.
${\bf(R4)}$ Suppose that a regular graph $G$ is uniquely defined by its
Laplacian spectrum. Does it necessarily mean that $G^{xyz}$ is also uniquely
defined by its Laplacian spectrum for every (or for some) $x,y,z\in\\{+,-\\}$
?
Acknowledgement:

Aiping Deng wishes to thank Michel Deza, Sergey V. Savchenko and Yaokun Wu for
their kind help to bring about the cooperation with Alexander Kelmans. We are
thankful to the referees for useful remarks.

## References

  * [1] J.A. Bondy, U.S.R. Murty, _Graph Theory_ , 3rd Corrected Printing, GTM 244, Springer-Verlag, New York, 2008.
  * [2] D.M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs: theory and applications, 3rd ed., Johann Ambrosius Barth Verlag, Heidelberg, Leipzig, 1995.
  * [3] A. Deng, I. Sato, Y. Wu, Homomorphisms, representations and characteristic polynomials of digraphs, _Linear Algebra Appl._ 423 (2007) 386-407.
  * [4] A. Deng, Y. Wu, Chracteristic polynomials of digraphs having a semi-free action, _Linear Algebra Appl._ 408 (2005) 189-206.
  * [5] R. Deistel, Graph Theory, Springer-Verlag, New York, 2005.
  * [6] F.R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1959.
  * [7] J.L. Gross, T.W. Tucker, Topological Graph Theory, Wiley, New York, 1987.
  * [8] R.A. Horn, C.R. Johnson, _Matrix Analysis_ , Cambridge University Press, 1992.
  * [9] A. Kelmans, On graph closures, Discrete Math. 271 (2003) 141-168.
  * [10] A. Kelmans, Transformations of a graph increasing its Laplacian polynomials and the number of trees, Europian Journal of Combinatorics 18 (1997) 35-48.
  * [11] A. Kelmans, On graphs with the maximum number of spanning trees, Random Structures and Algorithms 9 (1996) 177-192.
  * [12] A. Kelmans, Comparison of graphs by their probability of connectivity, In Kombinator. Asympt. Analiz, Krasnoyarsk (1977) 69–81.
  * [13] A. Kelmans, Operations on graphs that increase the number of their spanning trees, Issledovaniya po Discretnoy Optimizacii, Nauka, Moscow (1976) 406-424.
  * [14] A. Kelmans, On the determination of the eigenvalues of some special matrices, Ekonomika i Matematicheskie Metodi 8 (2) (1972) 266-272.
  * [15] A. Kelmans, Properties of the characteristic polynomial of a graph, _Kibernetiky - na sluzbu kommunizmu_ 4, Energija, Moskva - Leningrad, (1967) 27-41.
  * [16] A. Kelmans, The number of trees in a graph I and II, _Avtomat. i Telemeh._ 12 (1965) 2194-2204 and 2 (1966) 56-65 [in Russian] (English translation in: _Automat. Remote Control_ , 26 (1965)) and 27 (1966)).
  * [17] Q. Lin, J. Shu, Regularity and spectral radius of transformation graphs, _OR Trans._ 11 (2007) 102-110.
  * [18] J. Liu, J. Meng, Spectra of transformation digraphs of regular digraph, _Linear and Multilinear Algebra_ 58 (2010) 555-561.
  * [19] H. Mizuno, I. Sato, Characteristic polynomials of some graph covering, _Discrete Math._ 142 (1995) 295-298.
  * [20] B. Mohar, The Laplacian spectrum of graphs, _Graph Theory, Combinatorics, and Applications_ Vol. 2, Y. Alavi, G. Chartrand, O.R. Oellermann and A.J. Schwenk, eds., Wiley (1991) 871-898.
  * [21] M.W. Newman, The Laplacian spectrum of graphs, Master diss., University of Manitoba, Canada (2000).
  * [22] D. West, Introduction to Graph Theory, Prentice Hall, 2001.
  * [23] B. Wu, L. Zhang, Z. Zhang, The transformation graph $G^{xyz}$ when $xyz=-++$, _Discrete Math._ 296 (2005) 263-270.
  * [24] B. Wu, J. Meng, Basic properties of total transformation graphs, _J. Math. Study._ 34 (2001) 121-130.
  * [25] Y. Wu, Invariant subspace, determinant and characteristic polynomials, _Linear Algebra and its Appl._ 428 (2008) 1753-1760.
  * [26] J. Yan, K. Xu, Spectra of transformation graphs of regular graph, _Applied Mathematics, A Journal of Chinese Universities_ (Ser.A) 23 (2008) 476-480.
  * [27] F. Zhang, G. Lin, J. Meng, The characteristic polynomials of digraphs formed by some unary operations. _J. Xinjiang Univ. (Natural Science Edition)_ 4 (1987) 1-6.

Appendix

Let $G$ be an $r$-regular graph with $n$ vertices and $m$ edges and let
$s=n+m$, and so $2m=rn$ and $s$ is the number of vertices of $G^{xyz}$. The
tables below provide the formulas for $L(\lambda,G^{xyz})$ and $t(G^{xyz})$
for all $x,y,z\in\\{0,1,+,-\\}$ in terms of $n$, $m$, $r$, and the Laplacian
eigenvalues of $G$. Obviously, $t(G^{xyz})=0$ if and only if $G^{xyz}$ is not
connected. Note that for $z=0$, graph $G^{xyz}$ is not connected, and so
$t(G^{xyz})=0$. For $z=1$, graph $G^{xyz}$ is connected, and so
$t(G^{xyz})>0$.
The list of  $L(\lambda,G^{xyz})$ and $t(G^{xyz})$ with $z=0$.
$xyz$ $L(\lambda,G^{xyz})$ $t(G^{xyz})$ 1 $0~{}0~{}0$ $\lambda^{m+n}$ 0 2
$1~{}0~{}0$ $\lambda^{m+1}(\lambda-n)^{n-1}$ 0 3 $+0~{}0$
$\lambda^{m}L(\lambda,G)$ 0 4 $-0~{}0$
$(-1)^{n}(\lambda-n)^{-1}\lambda^{m+1}L(n-\lambda,G)$ 0 5 $0~{}1~{}0$
$\lambda^{n+1}(\lambda-m)^{m-1}$ 0 6 $1~{}1~{}0$
$\lambda^{2}(\lambda-m)^{m-1}(\lambda-n)^{n-1}$ 0 7 $+1~{}0$
$\lambda(\lambda-m)^{m-1}L(\lambda,G)$ 0 8 $-1~{}0$
$(-1)^{n}\lambda^{2}(\lambda-n)^{-1}(\lambda-m)^{m-1}L(n-\lambda,G)$ 0 9 $0+0$
$\lambda^{n}(\lambda-2r)^{m-n}L(\lambda,G)$ 0 10 $1+0$
$\lambda(\lambda-n)^{n-1}(\lambda-2r)^{m-n}L(\lambda,G)$ 0 11 $++0$
$(\lambda-2r)^{m-n}L(\lambda,G)^{2}$ 0 12 $-+0$
$(-1)^{n}(\lambda-2r)^{m-n}\lambda(\lambda-n)^{-1}L(n-\lambda,G)L(\lambda,G)$
0 13 $0-0$
$(-1)^{n}(\lambda-m)^{-1}\lambda^{n+1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)$ 0 14
$1-0$
$(-1)^{n}(\lambda-m)^{-1}\lambda^{2}(\lambda-n)^{n-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)$
0 15 $+-0$
$(-1)^{n}\lambda(\lambda-m)^{-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)L(\lambda,G)$
0 16 $--0$
$\lambda^{2}(\lambda-m)^{-1}(\lambda-n)^{-1}(\lambda-m+2r)^{m-n}L(m-\lambda,G)L(n-\lambda,G)$
0

The list of  $L(\lambda,G^{xyz})$ and $t(G^{xyz})$ with $z=1$.
$xyz$ $L(\lambda,G^{xyz})$ $t(G^{xyz})$ 1 $0~{}0~{}1$
$\lambda(\lambda-s)(\lambda-n)^{m-1}(\lambda-m)^{n-1}$ $n^{m-1}m^{n-1}$ 2
$1~{}0~{}1$ $\lambda(\lambda-s)^{n}(\lambda-n)^{m-1}$ $n^{m-1}s^{n-1}$ 3
$+0~{}1$ $(\lambda-m)^{-1}(\lambda-s)(\lambda-n)^{m-1}L(\lambda-m,G)$
$n^{m-1}\prod_{i=1}^{n-1}(m+\lambda_{i})$
$=\lambda(\lambda-s)(\lambda-n)^{m-1}\prod_{i=1}^{n-1}(\lambda-m-\lambda_{i})$
4 $-0~{}1$ $(-1)^{n}\lambda(\lambda-n)^{m-1}L(s-\lambda,G)$
$n^{m-1}\prod_{i=1}^{n-1}(s-\lambda_{i})$
$=\lambda(\lambda-s)(\lambda-n)^{m-1}\prod_{i=1}^{n-1}(\lambda-s+\lambda_{i})$
5 $0~{}1~{}1$ $\lambda(\lambda-s)^{m}(\lambda-m)^{n-1}$ $s^{m-1}m^{n-1}$ 6
$1~{}1~{}1$ $\lambda(\lambda-s)^{s-1}$ $s^{s-2}$ 7 $+1~{}1$
$\lambda(\lambda-m)^{-1}(\lambda-s)^{m}L(\lambda-m,G)$
$s^{m-1}\prod_{i=1}^{n-1}(m+\lambda_{i})$
$=\lambda(\lambda-s)^{m}\prod_{i=1}^{n-1}(\lambda-m-\lambda_{i})$ 8 $-1~{}1$
$(-1)^{n}\lambda(\lambda-s)^{m-1}L(s-\lambda,G)$
$s^{m-1}\prod_{i=1}^{n-1}(s-\lambda_{i})$
$=\lambda(\lambda-s)^{m}\prod_{i=1}^{n-1}(\lambda-s+\lambda_{i})$ 9 $0+1$
$\lambda(\lambda-s)(\lambda-n)^{-1}(\lambda-m)^{n-1}$
$m^{n-1}(n+2r)^{m-n}\prod_{i=1}^{n-1}(n+\lambda_{i})$
$(\lambda-n-2r)^{m-n}L(\lambda-n,G)$ 10 $1+1$
$\lambda(\lambda-n)^{-1}(\lambda-s)^{n}(\lambda-n-2r)^{m-n}$
$s^{n-1}(n+2r)^{m-n}$ $L(\lambda-n,G)$ $\prod_{i=1}^{n-1}(n+\lambda_{i})$ 11
$++1$ $\lambda(\lambda-s)(\lambda-m)^{-1}(\lambda-n)^{-1}$ $(n+2r)^{m-n}$
$(\lambda-n-2r)^{m-n}L(\lambda-m,G)L(\lambda-n,G)$
$\prod_{i+1}^{n-1}(m+\lambda_{i})(n+\lambda_{i})$ 12 $-+1$
$\lambda(\lambda-n)^{-1}(\lambda-n-2r)^{m-n}$ $(n+2r)^{m-n}$
$L(\lambda-n,G)L(s-\lambda,G)$
$\prod_{i=1}^{n-1}(n+\lambda_{i})(s-\lambda_{i})$ 13 $0-1$
$(-1)^{n}\lambda(\lambda-m)^{n-1}(\lambda-s+2r)^{m-n}L(s-\lambda,G)$
$m^{n-1}(s-2r)^{m-n}\prod_{i=1}^{n-1}(s-\lambda_{i})$ 14 $1-1$
$(-1)^{n}\lambda(\lambda-s)^{n-1}(\lambda-s+2r)^{m-1}L(s-\lambda,G)$
$s^{n-1}(s-2r)^{m-n}\prod_{i=1}^{n-1}(s-\lambda_{i})$ 15 $+-1$
$(-1)^{n}\lambda(\lambda-m)^{-1}(\lambda-s+2r)^{m-n}$ $(s-2r)^{m-n}$
$L(s-\lambda,G)L(\lambda-m,G)$
$\prod_{i=1}^{n-1}(s-\lambda_{i})(m+\lambda_{i})$ 16 $--1$
$\lambda(\lambda-s)^{-1}(\lambda-s+2r)^{m-n}L(s-\lambda,G)^{2}$
$(s-2r)^{m-n}\prod_{i=1}^{n-1}(s-\lambda_{i})^{2}$

The list of  $L(\lambda,G^{xyz})$ and  $t(G^{xyz})$ with  $z=+$.
$xyz$ $L(\lambda,G^{xyz})$ $t(G^{xyz})$ 1 $0~{}0+$
$\lambda(\lambda-r-2)(\lambda-2)^{m-n}\prod_{i=1}^{n-1}\\{\lambda^{2}-\lambda(r+2)+\lambda_{i}\\}$
$ns^{-1}(r+2)2^{m-n}t(G)$ 2 $1~{}0+$ $\lambda(\lambda-r-2)(\lambda-2)^{m-n}$
$s^{-1}(r+2)2^{m-n}\prod_{i=1}^{n-1}(2n+\lambda_{i})$
$\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-n-r)-2r+\lambda_{i}\\}$ 3 $+0+$
$\lambda(\lambda-r-2)(\lambda-2)^{m-n}$ $ns^{-1}(r+2)2^{m-n}3^{n-1}t(G)$
$\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-r-\lambda_{i})-2r+\lambda_{i}\\}$ 4
$-0+$ $\lambda(\lambda-r-2)(\lambda-2)^{m-n}$
$s^{-1}(r+2)2^{m-n}\prod_{i=1}^{n-1}(2n-\lambda_{i})$
$\prod_{i=1}^{n-1}\\{(\lambda-2)(\lambda-n-r+\lambda_{i})-2r+\lambda_{i}\\}$ 5
$0~{}1+$ $\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}$ $s^{-1}(r+2)(m+2)^{m-n}$
$\prod_{i=1}^{n-1}(\lambda-r)(\lambda-m-2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mr+\lambda_{i})$ 6 $1~{}1+$
$\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}$ $s^{-1}(r+2)(m+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-n-r)(\lambda-m-2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mn+2n+mr+\lambda_{i})$ 7 $+1+$
$\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}$ $s^{-1}(r+2)(m+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-m-2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mr+m\lambda_{i}+3\lambda_{i})$ 8 $-1+$
$\lambda(\lambda-r-2)(\lambda-m-2)^{m-n}$ $s^{-1}(r+2)(m+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-n-r+\lambda_{i})(\lambda-m-2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mr+mn+2n-m\lambda_{i}-\lambda_{i})$ 9 $0++$
$\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}$
$ns^{-1}(r+2)2^{m-n}(r+1)^{m-1}t(G)$
$\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$ 10
$1++$ $\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}$ $s^{-1}(r+2)(2r+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-n-r)(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}\\{2n+\lambda_{i}(n+r+1)\\}$ 11 $+++$
$\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}$ $ns^{-1}(r+2)(2r+2)^{m-n}t(G)$
$\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(r+3+\lambda_{i})$ 12 $-++$
$\lambda(\lambda-r-2)(\lambda-2r-2)^{m-n}$ $s^{-1}(r+2)(2r+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-
n-r+\lambda_{i})(\lambda-2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{i-1}(2n+\lambda_{i}(n+r-1-\lambda_{i}))$ 13 $0-+$
$\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}$ $s^{-1}(r+2)(m-2r+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-r)(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mr+\lambda_{i}r+\lambda_{i})$ 14 $1-+$
$\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}$ $s^{-1}(r+2)(m-2r+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-n-r)(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}\\{mn+2n+mr-\lambda_{i}(n+r-1)\\}$ 15 $+-+$
$\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}$ $s^{-1}(r+2)(m-2r+2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-r-\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}\\{mr+\lambda_{i}(m-r+3-\lambda_{i})\\}$ 16 $--+$
$\lambda(\lambda-r-2)(\lambda-m+2r-2)^{m-n}\prod_{i=1}^{n-1}$
$s^{-1}(r+2)(m-2r+2)^{m-n}\prod_{i=1}^{n-1}\\{mn$ $\\{(\lambda-
n-r+\lambda_{i})(\lambda-m-2+\lambda_{i})-2r+\lambda_{i}\\}$
$+2n+mr+\lambda_{i}(\lambda_{i}-m-n-r-1)\\}$

The list of  $L(\lambda,G^{xyz})$ and  $t(G^{xyz})$ with  $z=-$.
$xyz$ $L(\lambda,G^{xyz})$ $t(G^{xyz})$ 1 $0~{}0-$
$\lambda(\lambda-s+r+2)(\lambda-n+2)^{m-n}$ $s^{-1}(s-r-2)(n-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r)(\lambda-n+2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mn-nr-2m+\lambda_{i})$ 2 $1~{}0-$
$\lambda(\lambda-s+r+2)(\lambda-n+2)^{m-n}$ $s^{-1}(s-r-2)(n-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r)(\lambda-n+2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(ns-nr-2s+\lambda_{i})$ 3 $+0-$
$\lambda(\lambda-s+r+2)(\lambda-n+2)^{m-n}$ $s^{-1}(s-r-2)(n-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r-\lambda_{i})(\lambda-n+2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(mn-nr-2m+n\lambda_{i}-\lambda_{i})$ 4 $-0-$
$\lambda(\lambda-s+r+2)(\lambda-n+2)^{m-n}$ $s^{-1}(s-r-2)(n-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-n+2)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(ns-nr-2s-n\lambda_{i}+3\lambda_{i})$ 5 $0~{}1-$
$\lambda(\lambda-s+r+2)(\lambda-s+2)^{m-n}$ $s^{-1}(s-r-2)(s-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+2)(\lambda-m+r)-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(ms-rs-2m+\lambda_{i})$ 6 $1~{}1-$
$\lambda(\lambda-s+r+2)(\lambda-s+2)^{m-n}$ $s^{-1}(s-r-2)(s-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s)(\lambda-s+r+2)+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(s(s-r-2)+\lambda_{i})$ 7 $+1-$
$\lambda(\lambda-s+r+2)(\lambda-s+2)^{m-n}$ $s^{-1}(s-r-2)(s-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+2)(\lambda-m+r-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(s(m-r+\lambda_{i})-2m-\lambda_{i})$ 8 $-1-$
$\lambda(\lambda-s+r+2)(\lambda-s+2)^{m-n}$ $s^{-1}(s-r-2)(s-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+2)(\lambda-s+r+\lambda_{i})-2r+3\lambda_{i}\\}$
$\prod_{i=1}^{n-1}(s(s-r-\lambda_{i}-2)+\lambda_{i})$ 9 $0+-$
$\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}$ $s^{-1}(s-r-2)(n+2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r)(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((m-r)(n+\lambda_{i})-2m+\lambda_{i})$ 10 $1+-$
$\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}$ $s^{-1}(s-r-2)(n+2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r)(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((s-r)(n+\lambda_{i})-2s+\lambda_{i})$ 11 $++-$
$\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}$ $s^{-1}(s-r-2)(n+2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r-\lambda_{i})(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((m-r+\lambda_{i})(n+\lambda_{i})-2m-\lambda_{i})$ 12 $-+-$
$\lambda(\lambda-s+r+2)(\lambda-n-2r+2)^{m-n}$ $s^{-1}(s-r-2)(n+2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-n+2-\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((s-r-\lambda_{i})(n+\lambda_{i})-2s+3\lambda_{i})$ 13 $0--$
$\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}$ $s^{-1}(s-r-2)(s-2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r)(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((m-r)(s-\lambda_{i})-2m+\lambda_{i})$ 14 $1--$
$\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}$ $s^{-1}(s-r-2)(s-2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r)(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((s-r)(s-\lambda_{i})-2s+\lambda_{i})$ 15 $+--$
$\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}$ $s^{-1}(s-r-2)(s-2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-m+r-\lambda_{i})(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((m-r+\lambda_{i})(s-\lambda_{i})-2m-\lambda_{i})$ 16 $---$
$\lambda(\lambda-s+r+2)(\lambda-s+2r+2)^{m-n}$ $s^{-1}(s-r-2)(s-2r-2)^{m-n}$
$\prod_{i=1}^{n-1}\\{(\lambda-s+r+\lambda_{i})(\lambda-s+2+\lambda_{i})-2r+\lambda_{i}\\}$
$\prod_{i=1}^{n-1}((s-r-\lambda_{i})(s-\lambda_{i})-2s+3\lambda_{i})$