On linear layouts of graphs.
On line-symmetric graphs
On linguistic dynamical systems, families of graphs of large girth, and cryptography.
On local properties of graphs again
On local structure of 1-planar graphs of minimum degree 5 and girth 4
A graph is 1-planar if it can be embedded in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree 5 and girth 4 contains (1) a 5-vertex adjacent to an ≤ 6-vertex, (2) a 4-cycle whose every vertex has degree at most 9, (3) a with all vertices having degree at most 11.
On locally quasiconnected graphs and their upper embeddability
On locally tree-like graphs
On locating and differentiating-total domination in trees
A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let and be the minimum cardinality of a locating-total dominating set and a differentiating-total...
On locating-domination in graphs
A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number is the minimum cardinality of a LDS of G, and the upper locating-domination number, is the maximum cardinality of a minimal LDS of G. We present different bounds on and .
On long cycles through four prescribed vertices of a polyhedral graph
For a 3-connected planar graph G with circumference c ≥ 44 it is proved that G has a cycle of length at least (1/36)c+(20/3) through any four vertices of G.
On longest circuits in certain non-regular planar graphs
On Longest Cycles in Essentially 4-Connected Planar Graphs
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...
On longest paths and circuits in graphs.
On longest paths in connected graphs
On magic and supermagic line graphs
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.
On magic graphs
On magic joins of 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.
On magic labellings of -prisms
On magic labellings of type for three classes of plane graphs
On mapping graphs and permutation graphs