A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of such matchings, respectively, and are known to be NP-hard to compute. In this paper, we study the relationship between these two parameters and the matching number. In particular, we discuss the complexity of two decision problems; first: deciding if the matching number and disconnected matching number are equal; second: deciding if the disconnected matching number and induced matching number are equal. We show that given a bipartite graph with diameter four, deciding if the matching number and disconnected matching number are equal is NP-complete; the same holds for bipartite graphs with maximum degree three. We characterize diameter three graphs with equal matching number and disconnected matching number, which yields a polynomial time recognition algorithm. Afterwards, we show that deciding if the induced and disconnected matching numbers are equal is co-NP-complete for bipartite graphs of diameter 3. When the induced matching number is large enough compared to the maximum degree, we characterize graphs where these parameters are equal, which results in a polynomial time algorithm for bounded degree graphs.

A graph is an interval graph if its vertex set corresponds to a family of intervals on the real line, called a model, such that two distinct vertices are adjacent in the graph if and only if their corresponding intervals intersect each other. The minimum number of interval lengths that suffices to represent a model of a given interval graph is its interval count. The use of mathematical optimization techniques for solving interval count problems was first explored by Joos et al.[1]. In more detail, given a bipartition of vertices into classes of lengths, the authors propose an efficient linear programming based algorithm for solving the interval count two problem. However, so far, no mathematical formulation exists in the literature for general interval count. As a contribution in that direction, we introduce a mixed integer programming formulation for the exact value of interval count, parameterized by the largest interval length. Additionally, we also propose a quadratic formulation for a valid upper bound on interval count. Solution algorithms for these formulations were tested on interval count instances found in the literature. As an outcome of these experiments, the algorithm for the upper bound formulation was shown to run much faster than its exact solution counterpart. Furthermore, the upper bounds thus obtained were frequently certified as optimal by the exact algorithm.

We are interested in embedding trees T with ∆(T) ≤ 4 in a rectangular grid, such that the vertices of T correspond to grid points, while edges of T correspond to non-intersecting straight segments of the grid lines. Such embeddings are called straight models. While each edge is represented by a straight segment, a path of T is represented in the model by the union of the segments corresponding to its edges, which may consist of a path in the model having several bends. The aim is to determine a straight model of a given tree T minimizing the maximum number of bends over all paths of T. We provide a quadratic-time algorithm for this problem. We also show how to construct straight models that have k as its minimum number of bends and with the least number of vertices possible. As an application of our algorithm, we provide an upper bound on the number of bends of EPG models of VPT ∩ EPT graphs.

Software control is a critical issue in cyber-physical systems (CPS); if the expected behavior of the software embedded in a single device of a CPS cannot be enforced then the behavior of the whole CPS may be in jeopardy. Thus, CPS stakeholders like having some level of control over the embedded software. Third-party demands to control the software, however, conflict with the intellectual property protection demanded by software developers, since some level of detail about the software at hand would have to be disclosed. In the present paper, we discuss the issue of controlling the software embedded in CPS devices and address the problem of how to achieve an increased level of software control without compromising the protection of intellectual property. We propose a two-party fingerprinting scheme that allows for attribution of responsibility in the case of intellectual property leaks. Our fingerprinting scheme is such that neither party may obtain an advantage over the other by misbehaving, misrepresenting or by prematurely aborting the protocol, therefore providing a fair means to resolve disputes.

Digital watermarks embed information into a host artifact in such a way that the functionalities of the artifact remain unchanged. Allowing for the timely retrieval of authorship/ownership information, and ideally hard to be removed, watermarks discourage piracy and have thus been regarded as important tools to protect the intellectual property. A watermark aimed at uniquely identifying an artifact is referred to as a fingerprint. After presenting a formal definition of digital watermarks, we introduce an unbiased fingerprinting protocol -- based on oblivious transfer -- that lends no advantage to the prosecuting party in a dispute around intellectual property breach.

Let $G$ be a finite, simple, and undirected graph and let $S$ be a set of vertices of $G$. If no vertex of $G$ that does not belong to $S$ has two neighbors in $S$, then $S$ is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ of $S$ is the smallest $P_3$-convex set containing $S$. The $P_3$-Carathéodory number of $G$ is the smallest integer $c$ such that for every set $S$ and every vertex $u$ in $H_G(S)$, there is a set $F\subseteq S$ with $|F|\leq c$ and $u\in H_G(F)$. We study structural and algorithmic aspects of the $P_3$-Carathéodory number. We characterize the $P_3$-Carathéodory number of trees and block graphs, establish upper bounds on the $P_3$-Carathéodory number of general graphs and of claw-free graphs, and prove that it is NP-complete to decide for a given bipartite graph $G$ and a given integer $k$ whether the $P_3$-Carathéodory number of $G$ is at least $k$.

For \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $n\in \mathbb{N}$ \end{document} and \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $D\subseteq \mathbb{N}$ \end{document}, the distance graph P has vertex set {0,1,…,n − 1} and edge set {ij | 0 ≤ i,j ≤ n − 1,|j − i| ∈ D}. The class of distance graphs generalizes the important and very well-studied class of circulant graphs, which have been proposed for numerous network applications. In view of fault tolerance and delay issues in these applications, the connectivity and diameter of circulant graphs have been studied in great detail. Our contributions are hardness results concerning computational problems related to the connectivity and the diameter of distance graphs and a characterization of the connected distance graphs P for |D| = 2. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 310-315 2011

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number $h(G)$ of a graph G is the smallest cardinality of a set of vertices whose convex hull is the vertex set of G. For a connected triangle-free graph G of order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ if G has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if G is cubic. Furthermore for a connected graph G of order n, girth g at least 5, minimum degree at least 2, and diameter d, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.

In a recent paper, Durán et al. [J. Algorithms, 58 (2006), pp. 67–78] described an algorithm of complexity $O(n^2)$ for recognizing whether a graph G with n vertices and m edges is a unit circular-arc (UCA) graph. Furthermore, the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for G in polynomial time? (ii) Is it possible to construct a UCA model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size $O(n)$. The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities $O(n+m)$. Furthermore, the complexities reduce to $O(n)$, if a proper circular-arc (PCA) model of G is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of G can be constructed in $O(n+m)$ time, using the algorithm by Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390–403]. Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs.

Clique graphs of chordal and path graphs are characterized. A special class of graphs named expanded trees is discussed. It consists of a subclass of disk-Helly graphs. It is shown that the clique graph of every chordal (hence path) graph is an expanded tree. In addition, every expanded tree is the clique graph of some path (hence chordal) graph. Different characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing them.

Abstract A special class of reducible digraphs is characterized, those whose transitive reduction of the associated dag is a directed rooted tree. Polynomial time algorithms are described for the problems of recognition, isomorphism and finding minimum equivalent digraphs of this class. An approximative algorithm is also given for the general case of this last problem. The size of the approximation is always less than twice the exact solution. In addition, isomorphism of depth first search is solved as a special case of isomorphism of this class.

A grid graph is a node-induced finite subgraph of the infinite grid. It is rectangular if its set of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem is NP-complete.

Ternary search trees and ternary sequence search trees are defined as natural extensions of the binary case. Ternary tree insertion and its relation to topological sorting is also considered as a natural generalisation of binary tree insertion with its relationship to complete sorting. The problem of quasi-topological sorting, which can be regarded as a generalisation of topological sorting, is also solved using ternary trees. A possible definition of topological searching is presented. The analysis of ternary trees is given using recurrence relations.