Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Further results on the j-independence number of graphs1111447910.22049/cco.2022.28012.1417ENAhmedBouchouLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida,
AlgeriaMustaphaChellaliLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, AlgeriaJournal Article20220920In a graph $G$ of minimum degree $\delta$ and maximum degree $\Delta$, a subset $S$ of vertices of $G$ is $j$-independent, for some positive integer $j,$ if every vertex in $S$ has at most $j-1$ neighbors in $S$. The $j$-independence number $\beta_{j}(G)$ is the maximum cardinality of a $j$-independent set of $G$. We first establish an inequality between $\beta_{j}(G)$ and $\beta_{\Delta}(G)$ for $1\leq j\leq\delta-1$. Then we characterize all graphs $G$ with $\beta_{j}(G)=\beta_{\Delta}(G)$ for $j\in\{1,\dots,\Delta-1\}$, where the particular cases $j=1,2,\delta-1$ and<br />$\delta$ are well distinguished.https://comb-opt.azaruniv.ac.ir/article_14479_e04e66a5d2826a7c7f6179a4c1fc6ee6.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Uniqueness of rectangularly dualizable graphs13251444410.22049/cco.2022.27774.1350ENVinodKumarDepartment of Mathematics, Birla Institute of Technology & Science, Pilani, Pilani Campus, Rajasthan−333031, IndiaKrishnendraShekhawatDepartment of Mathematics, Birla Institute of Technology & Science, Pilani, Pilani Campus,
Rajasthan−333031, IndiaJournal Article20220418A generic rectangular partition is a partition of a rectangle into a finite number of rectangles provided that no four of them meet at a point. A graph $\mathcal{H}$ is called dual of a plane graph $\mathcal{G}$ if there is one$-$to$-$one correspondence between the vertices of $\mathcal{G}$ and the regions of $\mathcal{H}$, and two vertices of $\mathcal{G}$ are adjacent if and only if the corresponding regions of $\mathcal{H}$ are adjacent. A plane graph is a rectangularly dualizable graph if its dual can be embedded as a rectangular partition. A rectangular dual $\mathcal{R}$ of a plane graph $\mathcal{G}$ is a partition of a rectangle into $n-$rectangles such that (i) no four rectangles of $\mathcal{R}$ meet at a point, (ii) rectangles in $\mathcal{R}$ are mapped to vertices of $\mathcal{G}$, and (iii) two rectangles in $\mathcal{R}$ share a common boundary segment if and only if the corresponding vertices are adjacent in $\mathcal{G}$. In this paper, we derive a necessary and sufficient for a rectangularly dualizable graph $\mathcal{G}$ to admit a unique rectangular dual upto combinatorial equivalence. Further we show that $\mathcal{G}$ always admits a slicible as well as an area$-$universal rectangular dual.https://comb-opt.azaruniv.ac.ir/article_14444_9a3a14f51e2556463bdcb0f92c53612e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Some lower bounds on the Kirchhoff index27361445710.22049/cco.2022.27898.1389ENS.StankovFaculty of Electronic Engineering, University of Niš, Niš, SerbiaI.MilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaE.MilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaM.MatejićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaJournal Article20220625Let $G=(V,E)$, $V=\{v_1,v_2,\ldots,v_n\}$, $E=\{e_1,e_2,\ldots, e_m\}$, be a simple graph of order $n\ge 2$ and size $m$ without isolated vertices. Denote with $\mu_1\ge \mu_2\ge \cdots \ge \mu_{n-1}>\mu_n=0$ the Laplacian eigenvalues of $G$. The Kirchhoff index of a graph $G$, defined in terms of Laplacian eigenvalues, is given as $Kf(G) = n \sum_{i=1}^{n-1}\frac{1}{\mu_i}$. Some new lower bounds on $Kf(G)$ are obtained.https://comb-opt.azaruniv.ac.ir/article_14457_a58592a69e95194a03d5fd0935bb9d4c.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301On chromatic number and clique number in k-step Hamiltonian graphs37491446210.22049/cco.2022.27970.1407ENNoor A'lawiahAbd AzizSchool of Mathematical Sciences , Universiti Sains Malaysia, 11800 Penang, MalaysiaNaderJafari RadDepartment of Mathematics, Shahed University, Tehran, IranHailizaKamarulhailiSchool of Mathematical Sciences , Universiti Sains Malaysia, 11800 Penang, MalaysiaRoslanHasniFaculty of Ocean Engineering Technology and Informatics, Universiti Malaysia Terengganu, 21030 Kuala Nerus, Terengganu MalaysiaJournal Article20220822A graph $G$ of order $n$ is called $k-$step Hamiltonian for $k\geq 1$ if we can label the vertices of $G$ as $v_1,v_2,\ldots,v_n$ such that $d(v_n,v_1)=d(v_i,v_{i+1})=k$ for $i=1,2,\ldots,n-1$. The (vertex) chromatic number of a graph $G$ is the minimum number of colors needed to color the vertices of $G$ so that no pair of adjacent vertices receive the same color. The clique number of $G$ is the maximum cardinality of a set of pairwise adjacent vertices in $G$. In this paper, we study the chromatic number and the clique number in $k-$step Hamiltonian graphs for $k\geq 2$. We present upper bounds for the chromatic number in $k-$step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in $k-$step Hamiltonian graphs and characterize graphs achieving equality of the bound.https://comb-opt.azaruniv.ac.ir/article_14462_ad2836eddac7d6724175272ced1d03ce.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Chromatic transversal Roman domination in graphs51661446110.22049/cco.2022.27728.1346ENRoushini LeelyPushpamDepartment of Mathematics, D.B. Jain College, Chennai - 600 097, IndiaJournal Article20220409For a graph $G$ with chromatic number $k$, a dominating set $S$ of $G$ is called a chromatic-transversal dominating set (ctd-set) if $S$ intersects every color class of any $k$-coloring of $G$. The minimum cardinality of a ctd-set of $G$ is called the {\em chromatic transversal domination number} of $G$ and is denoted by $\gamma_{ct}(G)$. A {\em Roman dominating function} (RDF) in a graph $G$ is a function $f : V(G) \to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of a Roman dominating function is the value $w(f) = \sum_{u \in V} f(u)$. The minimum weight of a Roman dominating function of a graph $G$ is called the {\em Roman domination number} of $G$ and is denoted by $\gamma_R(G)$. The concept of {\em chromatic transversal domination} is extended to Roman domination as follows: For a graph $G$ with chromatic number $k$, a {\em Roman dominating function} $f$ is called a {\em chromatic-transversal Roman dominating function} (CTRDF) if the set of all vertices $v$ with $f(v) > 0$ intersects every color class of any $k$-coloring of $G$. The minimum weight of a chromatic-transversal Roman dominating function of a graph $G$ is called the {\em chromatic-transversal Roman domination number} of $G$ and is denoted by $\gamma_{ctR}(G)$. In this paper a study of this parameter is initiated.https://comb-opt.azaruniv.ac.ir/article_14461_8e5f54c16b4266f88af6f70ace2937d8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Simultaneous coloring of vertices and incidences of hypercubes67771461810.22049/cco.2023.27843.1367ENMahsaMozafari-NiaDepartment of Mathematical Sciences, Shahid Beheshti University,
G.C., P.O. Box 19839-63113, Tehran, IranMoharramN. IradmusaDepartment of Mathematical Sciences, Shahid Beheshti University,
G.C., P.O. Box 19839-63113, Tehran, IranJournal Article20220524An element $i=(v,e)$ of a graph $G$ is called an incidence of $G$, if $v\in V(G)$, $e\in E(G)$ and $v\in e$. The simultaneous coloring of vertices and incidences of a graph is coloring the vertices and incidences of the graph properly at the same time such that any two adjacent or incident elements receive distinct colors. In this paper, we investigate the simultaneous coloring of vertices and incidences of hypercubes.https://comb-opt.azaruniv.ac.ir/article_14618_faa7a557f561944ebf780cd7170ff722.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Bounds of point-set domination number79871444510.22049/cco.2022.27701.1319ENAlkaGoyalDepartment of Mathematics, University of Delhi, Delhi-110007, IndiaLakshmisreeBandopadhyayaDepartment of Mathematics, Deshbandhu College, University of Delhi, Delhi-110007, IndiaPurnimaGuptaDepartment of Mathematics, Sri Venkateswara College, University of Delhi, Delhi-110021, IndiaJournal Article20220225A subset $D$ of the vertex set $V(G)$ in a graph $G$ is a point-set dominating set (or, in short, psd-set) of $G$ if for every set $S\subseteq V- D$, there exists a vertex $v\in D$ such that the induced subgraph $\langle S\cup \{v\}\rangle$ is connected. The minimum cardinality of a psd-set of $G$ is called the point-set domination number of $G$. In this paper, we establish two sharp lower bounds for point-set domination number of a graph in terms of its diameter and girth. We characterize graphs for which lower bound of point set domination number is attained in terms of its diameter. We also establish an upper bound and give some classes of graphs which attains the upper bound of point set domination number.https://comb-opt.azaruniv.ac.ir/article_14445_c930b385ec9b08d09d98b41207553bf3.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Multiplicative Zagreb indices of trees with given domination number89991446810.22049/cco.2022.27972.1409ENTomasVetrikDepartment of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South AfricaMarcelAbasFaculty of Materials Science and Technology, Slovak University of Technology in Bratislava,
Trnava, SlovakiaJournal Article20220822In [On extremal multiplicative Zagreb indices of trees with given domination number, Applied Mathematics and Computation 332 (2018), 338--350] Wang et al. presented bounds on the multiplicative Zagreb indices of trees with given domination number. We fill in the gaps in their proofs of Theorems 3.1 and 3.3 and we correct Theorem 3.3.https://comb-opt.azaruniv.ac.ir/article_14468_ea98b7e5b1226ad9299589733587e9d0.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Bounds of Sombor index for corona products on $R$-graphs1011171445910.22049/cco.2022.27904.1391ENIshitaSarkarDepartment of Mathematics, CHRIST (Deemed to be University), Bengaluru 560029, IndiaManjunathNanjappaSchool of Engineering and Technology, CHRIST (Deemed to be University), Bengaluru 560074,
IndiaIvanGutmanFaculty of Science, University of Kragujevac, P.O.Box 60, 34000, Kragujevac, SerbiaJournal Article20220628Operations in the theory of graphs has a substantial influence in the analytical and factual dimensions of the domain. In the realm of chemical graph theory, topological descriptor serves as a comprehensive graph invariant linked with a specific molecular structure. The study on the Sombor index is initiated recently by Ivan Gutman. The triangle parallel graph comprises of the edges of subdivision graph along with the edges of the original graph. In this paper, we make use of combinatorial inequalities related with the vertices, edges and the neighborhood concepts as well as the other topological descriptors in the computations for the determination of bounds of Sombor index for certain corona products involving the triangle parallel graph.https://comb-opt.azaruniv.ac.ir/article_14459_727793a647a12a184e9f264e03c824f5.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301The energy and edge energy of some Cayley graphs on the abelian group $\mathbb{Z}_{n}^{4}$1191301458210.22049/cco.2023.28642.1647ENFatemeMovahediDepartment of Mathematics, Faculty of Sciences, Golestan University, Gorgan, IranJournal Article20230408Let $G=(V, E)$ be a simple graph such that $\lambda_1, \ldots, \lambda_n$ be the eigenvalues of $G$. The energy of graph $G$ is denoted by $E(G)$ and is defined as $E(G)=\sum_{i=1}^{n}|\lambda_{i}|$. The edge energy of $G$ is the energy of line graph $G$. In this paper, we investigate the energy and edge energy for two Cayley graphs on the abelian group $\mathbb{Z}_{n}^{4}$, namely, the Sudoku graph and the positional Sudoku graph. Also, we obtain graph energy and edge energy of the complement of these two graphs.https://comb-opt.azaruniv.ac.ir/article_14582_8ee43e8ba4a9d22b681d48db99808d70.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301On equitable near proper coloring of graphs1311431446310.22049/cco.2022.27240.1218ENSabithaJoseDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
IndiaLibin ChackoSamuelDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
IndiaSudevNaduvathDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
IndiaJournal Article20210502A defective vertex coloring of a graph is a coloring in which some adjacent vertices may have the same color. An edge whose adjacent vertices have the same color is called a bad edge. A defective coloring of a graph $G$ with minimum possible number of bad edges in $G$ is known as a near proper coloring of $G$. In this paper, we introduce the notion of equitable near proper coloring of graphs and determine the minimum number of bad edges obtained from an equitable near proper coloring of some graph classes.https://comb-opt.azaruniv.ac.ir/article_14463_aa03f3848854de27fc92f8e02e499257.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Tetravalent half-arc-transitive graphs of order $12p$1451571446910.22049/cco.2022.27990.1414ENM.GhasemiDepartment of Mathematics, Urmia University, Urmia 57135, IranN.MehdipoorDepartment of Mathematics, University of Mazandaran, Babolsar, IranA.A.TalebiDepartment of Mathematics, University of Mazandaran, Babolsar, IranJournal Article20220909A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not its arc set. In this paper, we study all tetravalent half-arc-transitive graphs of order $12p$, where $p$ is a prime.https://comb-opt.azaruniv.ac.ir/article_14469_d7551f5c25fe76588663191730a5a524.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Quasi total double Roman domination in trees1591681465010.22049/cco.2023.29008.1809ENMaryamAkhoundiClinical Research Development Unit of Rouhani Hospital, Babol University of Medical Sciences,
Babol 4717647745, IranAyshaKhanDepartment of Mathematics,
Prince Sattam bin Abdulaziz University,
Alkharj 11991, Saudi ArabiaJanaShafiDepartment of Computer Science,
College of Arts and Science,
Prince Sattam bin Abdul Aziz University,
Wadi Ad-Dwasir 11991, Saudi ArabiaLutzVolkmannRWTH Aachen University, 52056 Aachen, GermanyJournal Article20230610A quasi total double Roman dominating function (QTDRD-function) on a graph $G=(V(G),E(G))$ is a function $f:V(G)\longrightarrow\{0,1,2,3\}$ having the property that \textrm{(i)} if $f(v)=0$, then vertex $v$ must have at least two<br />neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$; \textrm{(ii)} if $f(v)=1$, then vertex $v$ has at least one neighbor $w$ with $f(w)\geq2$, and \textrm{(iii)} if $x$ is an isolated vertex in the subgraph induced by the set of vertices assigned non-zero values, then $f(x)=2$. The weight of a QTDRD-function $f$ is the sum of its function values over the whole vertices, and the quasi total double Roman domination number $\gamma_{qtdR}(G)$ equals the minimum weight of a QTDRD-function on $G$. In this paper, we show that for any tree $T$ of order $n\ge 4$, $\gamma_{qtdR}(T)\le n+\frac{s(T)}{2}$, where $s(T)$ is the number of support vertices of $T$, that improves a known bound.https://comb-opt.azaruniv.ac.ir/article_14650_47c1527b36f280949270620900469ef8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Maximizing the indices of a class of signed complete graphs1691751448410.22049/cco.2022.28103.1442ENNavidKafaiDepartment of Mathematics, Karaj Branch, Islamic Azad University, Karaj, IranFaridehHeydariDepartment of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran0000-0002-8944-4729Journal Article20221118The index of a signed graph is the largest eigenvalue of its adjacency matrix. Let $\mathfrak{U}_{n,k,4}$ be the set of all signed complete graphs of order $n$ whose negative edges induce a unicyclic graph of order $k$ and girth at least $4$. In this paper, we identify the signed graphs achieving the maximum index in the class $\mathfrak{U}_{n,k,4}$.https://comb-opt.azaruniv.ac.ir/article_14484_67642db4d3d22bc99a96418acadbdf2a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289120240301Extremal Kragujevac trees with respect to Sombor indices1771831450310.22049/cco.2023.28058.1430ENTsend-AyushSelengeDepartment of Mathematics, National University of Mongolia,
P.O.Box 187/46A, Ulaanbaatar, MongoliaBatmendHoroldagvaDepartment of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar, Mongolia0000-0003-3417-2612Journal Article20221029The concept of the Sombor indices of a graph was introduced by Gutman. A vertex-edge variant of the Sombor index of graphs is called the KG-Sombor index. Recently, the Sombor and KG-Sombor indices of Kragujevac trees were studied, and the extremal Kragujevac trees with respect to these indices were empirically determined. Here we give analytical proof of the results.https://comb-opt.azaruniv.ac.ir/article_14503_1e960bffbe2d564ae0c9dfb41bec1299.pdf