A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. We characterize magic line graphs of general graphs and describe some class of supermagic line graphs of bipartite graphs.
A graph is called magic (supermagic) if it admits a labeling of the edges by pairwise different (and consecutive) integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we characterize magic joins of graphs and we establish some conditions for magic joins of graphs to be supermagic.
We show that the pairs where T is a tree and its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or...
Let G be a connected graph. For two vertices u and v in G, a u-v geodesic is any shortest path joining u and v. The closed geodetic interval IG[u, v] consists of all vertices of G lying on any u-v geodesic. For S ⊆ V (G), S is a geodetic set in G if ∪u,v∈S IG[u, v] = V (G). Vertices u and v of G are neighbors if u and v are adjacent. The closed neighborhood NG[v] of vertex v consists of v and all neighbors of v. For S ⊆ V (G), S is a dominating set in G if ∪u∈S NG[u] = V (G). A geodetic dominating...
A graph G is a (Kq, k) stable graph (q ≥ 3) if it contains a Kq after deleting any subset of k vertices (k ≥ 0). Andrzej ˙ Zak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szyma´nski and Zwonek stating that for sufficiently large k the number of edges of a minimum (Kq, k) stable graph is (2q − 3)(k + 1) and that such a graph is isomorphic to sK2q−2 + tK2q−3 where s and t are integers such that s(q − 1) + t(q − 2) − 1 = k. We have proved (Fouquet...