Ding, Zongpeng Huang, Yuanqiu
Published in
Discussiones Mathematicae Graph Theory

There are only few results concerning crossing numbers of join of some graphs. In this paper, for some graphs on five vertices, we give the crossing numbers of its join with n isolated vertices.

Guterman, A.E. Maksaev, A.M.
Published in
Special Matrices

In this paper we characterize surjective linear maps on matrices over antinegative semirings that preserve the set of matrices with maximal or minimal positive values of the scrambling index.

Ouyang, Zhang Dong Wang, Jing Huang, Yuan Qiu
Published in
Discussiones Mathematicae Graph Theory

There are only few results concerning the crossing numbers of join of some graphs. In this paper, the crossing numbers of join products for the generalized Petersen graph P(3, 1) with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn are determined.

Oboudi, Mohammad Reza
Published in
Discussiones Mathematicae Graph Theory

Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)=∑k=0ns(G,k)xk $I(G,x) = \sum\nolimits_{k = 0}^n {s\left({G,k} \right)x^k }$ , where s(G, k) is the number of independent sets of G with size k and s(G, 0) = 1. A unicyclic graph i...

Ma, Fuhong Yan, Jin
Published in
Discussiones Mathematicae Graph Theory

In this paper, we prove that for an integer r ≥ 1, every regular tournament T of degree 3r − 1 contains at least 2116r-103 ${{21} \over {16}}r - {{10} \over 3}$ disjoint directed 4-cycles. Our result is an improvement of Lichiardopol’s theorem when taking q = 4 [Discrete Math. 310 (2010) 2567–2570]: for given integers q ≥ 3 and r ≥ 1, a tournament ...

Cockburn, Sally
Published in
Discussiones Mathematicae Graph Theory

A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism f : G → H. A geometric graph Ḡ is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. A geometric homomorphism (respectively, isomorphism) Ḡ → H̄ is a graph homomo...

Li, Wenjing Li, Xueliang Zhang, Jingshu
Published in
Discussiones Mathematicae Graph Theory

A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is define...

Changat, Manoj Hossein Nezhad, Ferdoos Mulder, Henry Martyn Narayanan, N.
Published in
Discussiones Mathematicae Graph Theory

In this note we extend the Mulder-Nebeský characterization of the interval function of a connected graph to the disconnected case. One axiom needs to be adapted, but also a new axiom is needed in addition.

Wang, Fan Zhao, Weisheng
Published in
Discussiones Mathematicae Graph Theory

Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ...

Hasegawa, Takehiro Saito, Seiken Sato, Iwao
Published in
Forum Mathematicum

In 1874, Franz Mertens proved the so-called Mertens’ theorem, and in 1974, Kenneth S. Williams showed Mertens’ theorem associated with a character. In a previous paper, we presented a graph-theoretic analogue to Williams’ theorem. In this paper, we generalize our previous work in the sense that a character is extended to a representation. To our kn...