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.
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.
A majority coloring of a digraph with colors is an assignment such that for every we have for at most half of all out-neighbors . A digraph is majority -choosable if for any assignment of lists of colors of size to the vertices, there is a majority coloring of from these lists. We prove that if is a 1-planar graph without a 4-cycle, then is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable.
In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the single-marginal problem and the marginal-representation problem) that were solved only for the special class of the so-called “canonical expressions”. We also show that the two problems can be solved “from scratch” with preliminary symbolic computation.
It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type if and only if it is Markov -convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property.
We show positivity of the Q-matrix of four kinds of graph products: direct product (Cartesian product), star product, comb product, and free product. During the discussion we give an alternative simple proof of the Markov product theorem on positive definite kernels.
A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial...
We give a graph theoretic interpretation of -Lah numbers, namely, we show that the -Lah number counting the number of -partitions of an -element set into ordered blocks is just equal to the number of matchings consisting of edges in the complete bipartite graph with partite sets of cardinality and (, ). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for -Stirling numbers of the second kind.