Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

Regularity of powers of bipartite graphs

Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs.     

On eigenvalues of Seidel matrices and Haemers’ conjecture

For a graph G, let S(G) be the Seidel matrix of G and \({\theta }_1(G),\ldots ,{\theta }_n(G)\) be the eigenvalues of S(G). The Seidel energy of G is defined as \(|{\theta }_1(G)|+\cdots +|{\theta }_n(G)|\). Willem Haemers conjectured that the Seidel energy of any graph with n vertices is at least \(2n-2\), the Seidel energy of the complete graph with n vertices. Motivated by this conjecture, we prove that for any \(\alpha \) with \(0<\alpha <2,|{\theta }_1(G)|^\alpha +\cdots +|{\theta }_n(G)|^\alpha \geqslant (n-1)^\alpha +n-1\) if and only if \(|\hbox {det}\,S(G)|\geqslant n-1\). This, in particular, implies the Haemers’ conjecture for all graphs G with \(|\hbox {det}\,S(G)|\geqslant n-1\). A computation on the fraction of graphs with \(|\hbox {det}\,S(G)|<n-1\) is reported. Motivated by that, we conjecture that almost all graphs G of order n satisfy \(|\hbox {det}\,S(G)|\geqslant n-1\). In connection with this conjecture, we note that almost all graphs of order n have a Seidel energy of order \(\Theta (n^{3/2})\). Finally, we prove that self-complementary graphs G of order \(n\equiv 1\pmod 4\) have \(\det S(G)=0\).     

Distance Magic Labeling in Complete 4-partite Graphs

Let G be a complete k-partite simple undirected graph with parts of sizes \(p_1\le p_2\cdots \le p_k\). Let \(P_j=\sum _{i=1}^jp_i\) for \(j=1,\ldots ,k\). It is conjectured that G has distance magic labeling if and only if \(\sum _{i=1}^{P_j} (n-i+1)\ge j{{n+1}\atopwithdelims (){2}}/k\) for all \(j=1,\ldots ,k\). The conjecture is proved for \(k=4\), extending earlier results for \(k=2,3\).     

Optimal channel assignment and <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function \(f:V(G)\rightarrow \{0,1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge p\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\ge 1\) if \(d(u,v)=2\), where d(u, v) is the distance between the two vertices u and v in the graph. Denote \(\lambda _{p,1}^l(G)= \min \{k \mid G\) has a list k-L(p, 1)-labeling\(\}\). In this paper we show upper bounds \(\lambda _{1,1}^l(G)\le \Delta +9\) and \(\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}\) for planar graphs G without 4- and 6-cycles, where \(\Delta \) is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Walk-Powers and Homomorphism Bounds of Planar Signed Graphs

As an extension of the Four-Color Theorem it is conjectured by the first author that every planar graph of odd-girth at least \(2k+1\) admits a homomorphism to the projective cube of dimension 2k, i.e., the Cayley graph \({\mathcal {PC}}(2k)=({\mathbb {Z}}_2^{2k}, \{e_1, e_2,\) \(\ldots ,e_{2k}, J\})\) where the \(e_i\)’s are the standard basis vectors of \({\mathbb {Z}}_2^d\) and J is the all 1 vector. Noting that \({\mathcal {PC}}(2k)\) itself is of odd-girth \(2k+1\), in this work we show that if the conjecture is true, then \({\mathcal {PC}}(2k)\) is an optimal such graph both with respect to the number of vertices and the number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for signed bipartite planar graphs of unbalanced-girth 2k. The work is presented in the uniform framework of planar consistent signed graphs.     

Edge Roman Domination on Graphs

An edge Roman dominating function of a graph G is a function \(f:E(G) \rightarrow \{0,1,2\}\) satisfying the condition that every edge e with \(f(e)=0\) is adjacent to some edge \(e'\) with \(f(e')=2\). The edge Roman domination number of G, denoted by \(\gamma '_R(G)\), is the minimum weight \(w(f) = \sum _{e\in E(G)} f(e)\) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree \(\Delta \) on n vertices, then \(\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil \). While the counterexamples having the edge Roman domination numbers \(\frac{2\Delta -2}{2\Delta -1} n\), we prove that \(\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}\) is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most \(\frac{6}{7}n\), which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain \(K_{2,3}\) as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.     

On the least distance eigenvalues of the second power of a graph

The k-th power of a graph G, denoted by \(G^k\), is the graph obtained from G by adding an edge between each pair of vertices with distance at most k. This paper investigates the least distance eigenvalues of the second power of a connected graph, and determine the trees and unicyclic graphs with least distance eigenvalues of the second power in \([-\,3,-\,2]\) and \((-\,\frac{3+\sqrt{5}}{2}, -\,1]\), respectively.     

Packing Chromatic Number of Base-3 Sierpiński Graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least \(i+1\). Let \(S^n\) be the base-3 Sierpiński graph of dimension n. It is proved that \(\chi _{\rho }(S^1) = 3\), \(\chi _{\rho }(S^2) = 5\), \(\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7\), and that \(8\le \chi _\rho (S^n) \le 9\) holds for any \(n\ge 5\).     

A generalization of total graphs

Let R be a commutative ring with nonzero identity, \(L_{n}(R)\) be the set of all lower triangular \(n\times n\) matrices, and U be a triangular subset of \(R^{n}\), i.e., the product of any lower triangular matrix with the transpose of any element of U belongs to U. The graph \(GT^{n}_{U}(R^n)\) is a simple graph whose vertices consists of all elements of \(R^{n}\), and two distinct vertices \((x_{1},\dots ,x_{n})\) and \((y_{1},\dots ,y_{n})\) are adjacent if and only if \((x_{1}+y_{1}, \ldots ,x_{n}+y_{n})\in U\). The graph \(GT^{n}_{U}(R^n)\) is a generalization for total graphs. In this paper, we investigate the basic properties of \(GT^{n}_{U}(R^n)\). Moreover, we study the planarity of the graphs \(GT^{n}_{U}(U)\), \(GT^{n}_{U}(R^{n}{\setminus } U)\) and \(GT^{n}_{U}(R^n)\).     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

Conformally Covariant Differential Operators for the Diagonal Action of $$O(p,\,q)$$ on Real Quadrics

Let \(X=G/P\) be a real projective quadric, where \(G=O(p,\,q)\) and P is a parabolic subgroup of G. Let \((\pi _{\lambda ,\epsilon },\, \mathcal H_{\lambda ,\epsilon })_{ (\lambda ,\epsilon )\in {\mathbb {C}}\times \{\pm \}}\) be the family of (smooth) representations of G induced from the characters of P. For \((\lambda ,\, \epsilon ),\, (\mu ,\, \eta )\in {\mathbb {C}}\times \{\pm \},\) a differential operator \(\mathbf D_{(\mu ,\eta )}^\mathrm{reg}\) on \(X\times X,\) acting G-covariantly from \({\mathcal {H}}_{\lambda ,\epsilon } \otimes {\mathcal {H}}_{\mu , \eta }\) into \({\mathcal {H}}_{\lambda +1,-\epsilon } \otimes {\mathcal {H}}_{\mu +1, -\eta }\) is constructed.     

Packing coloring of Sierpiński-type graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in \{1,\ldots ,k\}\), where each \(V_i\) is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs \(ST^n_3\) is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs \(S^n_G\) with respect to all connected graphs G of order 4.     

Vizing Bound for the Chromatic Number on Some Graph Classes

We are interested in hereditary classes of graphs \({\mathcal {G}}\) such that every graph \(G \in {\mathcal {G}}\) satisfies \(\varvec{\chi }(G) \le \omega (G) + 1\), where \(\chi (G)\) (\(\omega (G)\)) denote the chromatic (clique) number of G. This upper bound is called the Vizing bound for the chromatic number. Apart from perfect graphs few classes are known to satisfy the Vizing bound in the literature. We show that if G is (\(P_6, S_{1, 2, 2}\), diamond)-free, then \(\chi (G) \le \omega (G)+1\), and we give examples to show that the bound is sharp.     

Comparison of graphs associated to a commutative Artinian ring

Let R be a commutative ring with \(1\ne 0\) and the additive group \(R^+\). Several graphs on R have been introduced by many authors, among zero-divisor graph \(\Gamma _1(R)\), co-maximal graph \(\Gamma _2(R)\), annihilator graph AG(R), total graph \( T(\Gamma (R))\), cozero-divisors graph \(\Gamma _\mathrm{c}(R)\), equivalence classes graph \(\Gamma _\mathrm{E}(R)\) and the Cayley graph \(\mathrm{Cay}(R^+ ,Z^*(R))\). Shekarriz et al. (J. Commun. Algebra, 40 (2012) 2798–2807) gave some conditions under which total graph is isomorphic to \(\mathrm{Cay}(R^+ ,Z^*(R))\). Badawi (J. Commun. Algebra, 42 (2014) 108–121) showed that when R is a reduced ring, the annihilator graph is identical to the zero-divisor graph if and only if R has exactly two minimal prime ideals. The purpose of this paper is comparison of graphs associated to a commutative Artinian ring. Among the results, we prove that for a commutative finite ring R with \(|\mathrm{Max}(R)|=n \ge 3\), \( \Gamma _1(R) \simeq \Gamma _2(R)\) if and only if \(R\simeq \mathbb {Z}^n_2\); if and only if \(\Gamma _1(R) \simeq \Gamma _\mathrm{E}(R)\). Also the annihilator graph is identical to the cozero-divisor graph if and only if R is a Frobenius ring.     

The hyper-Zagreb index and some graph operations

Let G be a simple connected graph. The Hyper-Zagreb index is defined as \(\textit{HM}(G)=\sum _{uv\in E_{G}}(d_{G}(u)+d_{G}(v))^2\). In this paper some exact expressions for the hyper-Zagreb index of graph operations containing cartesian product and join of n graphs, splice, link and chain of graphs will be presented. We also apply these results to some graphs to chemical and general interest, such as \(C_4\) nanotube, rectangular grid, prism, complete n-partite graph.     

Structural Properties of Word Representable Graphs

Given a word \(w=w_1w_2\cdots w_n\) of length n over an ordered alphabet \(\Sigma _k\), we construct a graph \(G(w)=(V(w), E(w))\) such that V(w) has n vertices labeled \(1, 2,\ldots , n\) and for \(i, j \in V(w)\), \((i, j) \in E(w)\) if and only if \(w_iw_j\) is a scattered subword of w of the form \(a_{t}a_{t+1}\), \(a_t \in \Sigma _k\), for some \(1 \le t \le k-1\) with the ordering \(a_t<a_{t+1}\). A graph is said to be Parikh word representable if there exists a word w over \(\Sigma _k\) such that \(G=G(w)\). In this paper we characterize all Parikh word representable graphs over the binary alphabet in terms of chordal bipartite graphs. It is well known that the graph isomorphism (GI) problem for chordal bipartite graph is GI complete. The GI problem for a subclass of (6, 2) chordal bipartite graphs has been addressed. The notion of graph powers is a well studied topic in graph theory and its applications. We also investigate a bipartite analogue of graph powers of Parikh word representable graphs. In fact we show that for G(w), \(G(w)^{[3]}\) is a complete bipartite graph, for any word w over binary alphabet.     

Some infinite families of Ramsey ($${\varvec{P}}_\mathbf{3},{\varvec{P}}_{{\varvec{n}}}$$)-minimal trees

For any given two graphs G and H, the notation \(F\rightarrow \) (G, H) means that for any red–blue coloring of all the edges of F will create either a red subgraph isomorphic to G or a blue subgraph isomorphic to H. A graph F is a Ramsey (G, H)-minimal graph if \(F\rightarrow \) (G, H) but \(F-e\nrightarrow (G,H)\), for every \(e \in E(F)\). The class of all Ramsey (G, H)-minimal graphs is denoted by \(\mathcal {R}(G,H)\). In this paper, we construct some infinite families of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n=8\) and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n\ge 10\).     

Cliques in $$C_4$$-free graphs of large minimum degree

A graph G is called \(C_4\)-free if it does not contain the cycle \(C_4\) as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erd?s) a peculiar property of \(C_4\)-free graphs: \(C_4\)-free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least \(c'n\) (with \(c'= 0.1c^2\)). We prove here better bounds \(\big ({c^2n\over 2+c}\) in general and \((c-1/3)n\) when \( c \le 0.733\big )\) from the stronger assumption that the \(C_4\)-free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular \(C_4\)-free graphs on \(4k+1\) vertices contain a clique of size \(k+1\). This is the best possible as shown by the kth power of the cycle \(C_{4k+1}\).