An adjacent vertex distinguishing total k-coloring f of a graph G is a proper total k-coloring of G such that no pair of adjacent vertices has the same color sets. In 2005 Zhang et al. posted the ...conjecture (AVDTCC) that every simple graph G has adjacent vertex distinguishing total (∆(G) + 3)-coloring. In this paper we confirm the conjecture for many coronas, in particular for generalized, simple and l-coronas of graphs, not relating the results to particular graph classes.
The orientable domination number, DOM(G), of a graph G is the largest domination number over all orientations of G. In this paper, DOM is studied on different product graphs and related graph ...operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. (1996) is extended by establishing the values of DOM(Kn1,n2,n3) for arbitrary positive integers n1,n2 and n3. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in Brešar et al. (2022).
Recently, corona product graphs have attracted a great deal of attention from scientific communities, such as coding theory, frequency assignment, mathematical chemistry. Meanwhile, weight factor ...gradually became a research hotpoint because of closing to reality. Hence, we introduce the weighted corona graphs in this paper. The weighted corona product graphs are the in-depth and promotion of the corona product graphs, linking the spectra between the initial graph and the product graph. Then, we deduce the complete information of generalized adjacency and Laplacian eigenvalues of the weighted product graph with different structures. And we generalize the results obtained previously into product corona graph with m(⩾1) iterations.
•Laplacian spectra of the weighted corona product graphs.•The generalized adjacency eigenvalues of the weighted corona product graphs.•The spectra of the weighted corona product in a finite number of iterations.•Attaching copy graph is a regular graph and a complete bipartite graph.
A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer k ...for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by x=( G). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G◦ lH is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most x=( G◦ lH) + 1 colors in the remaining cases.
On the metric dimension of corona product graphs Yero, I.G.; Kuziak, D.; Rodríguez-Velázquez, J.A.
Computers & mathematics with applications (1987),
05/2011, Letnik:
61, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Given a set of vertices
S
=
{
v
1
,
v
2
,
…
,
v
k
}
of a connected graph
G
, the metric representation of a vertex
v
of
G
with respect to
S
is the vector
r
(
v
|
S
)
=
(
d
(
v
,
v
1
)
,
d
(
v
,
v
2
)
...,
…
,
d
(
v
,
v
k
)
)
, where
d
(
v
,
v
i
)
,
i
∈
{
1
,
…
,
k
}
denotes the distance between
v
and
v
i
.
S
is a resolving set for
G
if for every pair of distinct vertices
u
,
v
of
G
,
r
(
u
|
S
)
≠
r
(
v
|
S
)
. The metric dimension of
G
,
dim
(
G
)
, is the minimum cardinality of any resolving set for
G
. Let
G
and
H
be two graphs of order
n
1
and
n
2
, respectively. The corona product
G
⊙
H
is defined as the graph obtained from
G
and
H
by taking one copy of
G
and
n
1
copies of
H
and joining by an edge each vertex from the
i
th-copy of
H
with the
i
th-vertex of
G
. For any integer
k
≥
2
, we define the graph
G
⊙
k
H
recursively from
G
⊙
H
as
G
⊙
k
H
=
(
G
⊙
k
−
1
H
)
⊙
H
. We give several results on the metric dimension of
G
⊙
k
H
. For instance, we show that given two connected graphs
G
and
H
of order
n
1
≥
2
and
n
2
≥
2
, respectively, if the diameter of
H
is at most two, then
dim
(
G
⊙
k
H
)
=
n
1
(
n
2
+
1
)
k
−
1
dim
(
H
)
. Moreover, if
n
2
≥
7
and the diameter of
H
is greater than five or
H
is a cycle graph, then
dim
(
G
⊙
k
H
)
=
n
1
(
n
2
+
1
)
k
−
1
dim
(
K
1
⊙
H
)
.
For any integer $k\geq 3$ , we define sunlet graph of order $2k$, denoted by $L_{2k}$, as the graph consisting of a cycle of length $k$ together with $k$ pendant vertices, each adjacent to exactly ...one vertex of the cycle. In this paper, we give necessary and sufficient conditions for the existence of $L_{8}$-decomposition of tensor product and wreath product of complete graphs.
Let G be a graph having a unique perfect matching M,
be the adjacency matrix of G and
be the collection of all positive weight functions defined on the edge set of G in which each weight function w ...assigns weight 1 to each matching edge and a positive weight to each non-matching edge. The weighted graph
satisfies the
property if for each eigenvalue of
, its anti-reciprocal is also an eigenvalue of
with the same multiplicity. In this paper, a class of graphs with a unique perfect matching M for which the diagonal entries of the inverse of the adjacency matrix of each graph are all zero is investigated. Furthermore, it is shown that no noncorona graph in this class satisfies the
property even for a single weight function
.
The class of unicyclic $3$-colored digraphs with the cycle weight $\pm\mathrm{i}$ and with a unique perfect matching, denoted by $\mathcal{U}_g$, is considered in this article. Kalita \& Sarma On the ...inverse of unicyclic 3-coloured digraphs, Linear and Multilinear Algebra, DOI: 10.1080/03081087.2021.1948956 introduced the notion of inverse of $3$-colored digraphs. They characterized the unicyclic $3$-colored digraphs in $\mathcal{U}_g$ possessing unicyclic inverses. This article provides a complete characterization of the unicyclic $3$-colored digraphs in $\mathcal{U}_g$ possessing bicyclic inverses.
In the article 'Ahmad et al.' Class of weighted graphs with strong anti-reciprocal eigenvalue property. Linear Multilinear Algebra. 2018;68(6):1129-1139, Lemma 2.4 is not true in general case. In ...this note, we provide a counter example. Furthermore, it is observed that the result holds for graphs with property (-SR). Adding the assumption that G satisfies property (-SR) in the statement of Lemma 2.4, a new proof is provided for completeness.