An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.
We prove formulas for the generating functions for -rank differences for partitions without repeated odd parts. These formulas are in terms of modular forms and generalized Lambert series.
A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.
A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we prove that any balanced bipartite graph with minimum degree greater than |V(G)|/4 ≥ 2 is magic. A similar result is presented for supermagic regular bipartite graphs.
Necessary and sufficient conditions for a graph that its power , , is a magic graph and one consequence are given.
An eigenvalue of a real symmetric matrix is called main if there is an associated eigenvector not orthogonal to the all-1 vector . Main eigenvalues are frequently considered in the framework of simple undirected graphs. In this study we generalize some results and then apply them to signed graphs.