Search

An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G . The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e ( G ) . It follows that 1 ≤ dim e ( G ) ≤ n − 1 for any n -vertex graph G . A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O ( n 3 ) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful.

Daisy cubes are a recently introduced class of isometric subgraphs of hypercubes Q n . They are induced with intervals between chosen vertices of Q n and the vertex 0 n ∈ V ( Q n ) . In this paper we characterize daisy cubes in terms of an expansion procedure thus answering an open problem proposed by Klavžar and Mollard, 2019, in the introductory paper of daisy cubes (Klavžar and Mollard, 2019). To obtain such a characterization several interesting properties of daisy cubes are presented. For a given graph G isomorphic to a daisy cube, but without the corresponding embedding into a hypercube, we present an algorithm which finds a proper embedding of G into a hypercube in O ( m n ) time. Finally, daisy graphs of a rooted graph are introduced and shown to be a generalization of daisy cubes.

We introduce an apparatus to measure closeness or relationship of two given objects. This is a topology-based apparatus that uses graph representations of the compared objects. In more detail, we obtain a metric on the class of all pairwise non-isomorphic connected simple graphs to measure closeness of two such graphs. To obtain such a measure, we use the theory of hyperspaces from topology to introduce the notion of the Hausdorff graph \(2^G \) of any graph G. Then, using this new concept of Hausdorff graphs combined with the notion of graph amalgams, we present the Hausdorff distance, which proves to be useful when examining the closeness of any two connected simple graphs. We also present many possible applications of these concepts in various areas.

A subset S of vertices of a graph G is called a vertex k-path cover if every path of order k in G contains at least one vertex from S. Denote by @j"k(G) the minimum cardinality of a vertex k-path cover in G. In this paper, an upper bound for @j"3 in graphs with a given average degree is presented. A lower bound for @j"k of regular graphs is also proven. For grids, i.e. the Cartesian products of two paths, we give an asymptotically tight bound for @j"k and the exact value for @j"3.

Let $G=(V,E)$ be a connected graph. A vertex $w\in V$ distinguishes two elements (vertices or edges) $x,y\in E\cup V$ if $d_G(w,x)\ne d_G(w,y)$. A set $S$ of vertices in a connected graph $G$ is a mixed metric generator for $G$ if every two elements (vertices or edges) of $G$ are distinguished by some vertex of $S$. The smallest cardinality of a mixed metric generator for $G$ is called the mixed metric dimension and is denoted by $\mathrm{mdim}(G)$. In this paper we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results about the mixed metric dimension of some families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case., arXiv admin note: text overlap with arXiv:1602.00291

It is shown that the Clar number can be arbitrarily larger than the cardinality of a maximal alternating set. In particular, a maximal alternating set of a hexagonal system need not contain a maximum cardinality resonant set, thus disproving a previously stated conjecture. It is known that maximum cardinality resonant sets and maximal alternating sets are canonical, but the proofs of these two theorems are analogous and lengthy. A new conjecture is proposed and it is shown that the validity of the conjecture allows short proofs of the aforementioned two results. The conjecture holds for catacondensed hexagonal systems and for all normal hexagonal systems up to ten hexagons. Also, it is shown that the Fries number can be arbitrarily larger than the Clar number.

Fibonacci cubes are induced subgraphs of hypercubes based on Fibonacci strings. They were introduced to represent interconnection networks as an alternative to the hypercube networks. We derive a characterization of Fibonacci cubes founded on the concept of resonance graphs. The characterization is the basis for an algorithm which recognizes these graphs in O(mlog n) time.

A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$). Let $G$ be a graph whose vertices are coloured. A colouring $\varphi$ of the graph $G$ is non-repetitive if the sequence of colours on every path in $G$ is non-repetitive. The Thue chromatic number, denoted by $\pi (G)$, is the minimum number of colours of a non-repetitive colouring of $G$. In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product $G\circ H$ of graphs $G$ and $H$ with respect to some properties of the factors. This upper bound is then used to derive the exact values for $\pi(G\circ H)$ when $G$ is a complete multipartite graph and $H$ is an arbitrary graph.

Let G = ( V , E ) be a connected graph. The distance between two vertices u , v ∈ V , denoted by d ( u , v ) , is the length of a shortest u , v -path in G . The distance between a vertex v ∈ V and a subset P ⊂ V is defined as min { d ( v , x ) : x ∈ P } , and it is denoted by d ( v , P ) . An ordered partition { P 1 , P 2 , … , P t } of vertices of a graph G , is a resolving partition of G , if all the distance vectors ( d ( v , P 1 ) , d ( v , P 2 ) , … , d ( v , P t ) ) are different. The partition dimension of G is the minimum number of sets in any resolving partition of G . In this article we study the partition dimension of strong product graphs and Cartesian product graphs. Specifically, we prove that the partition dimension of the strong product of graphs is bounded below by four and above by the product of the partition dimensions of the factor graphs. Also, we give the exact value of the partition dimension of strong product graphs when one factor is a complete graph and the other one is a path or a cycle. For the case of Cartesian product graphs, we show that its partition dimension is less than or equal to the sum of the partition dimensions of the factor graphs minus one. Moreover, we obtain an upper bound on the partition dimension of Cartesian product graphs, when one factor is a complete graph.

Genetic algorithms are a computational paradigm belonging to the class of optimization techniques known as evolutionary computation. They have been implemented successfully to solve many difficult optimization problems. We have developed a new genetic algorithm for the maximum independent set problem based on the elitist strategy. The algorithm presented is tested on the so-called DIMACS benchmark graphs. The effectiveness of the algorithm is very satisfactory since it outperforms in most cases the genetic algorithms for the maximum independent set problem reported in the literature.

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekule structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the re- moval of the internal vertices and edges of the path that is the intersection of f and the outer cycle of G results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result gen- eralizes the characterization of reducible faces of an elementary benzenoid graph.

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n2) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψk(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ψk of the Cartesian and the strong product of paths are derived. It is shown that for ψ3 those bounds are tight. For the lexicographic product bounds are presented for ψk, moreover ψ2 and ψ3 are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.