Narrow Results

Generalized cubes are a subclass of hypercube-like networks that are employed by a number of parallel algorithms. Linear array is common topology of multicomputer system. So congestion is very useful to improve algorithm performance for implementing generalized cube communication pattern on linear array. This paper addresses the congestion of generalized cube communication patterns embedding into linear array topology. For this purpose, the maximum m-induced subgraph of generalized cube is determined firstly, which is very important for discussing the congestion. Then an embedding scheme is described, and the congestion is shown to attain the minimum, which guarantees the optimality of the proposed scheme.

The Network Construction problem, studied by Angluin et al., Hosoda et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set $V$ of vertices, construction costs for all possible edges between pairs of vertices from $V$, and a sequence $S_1,S_2,\dots ,S_r\subseteq V$ of connectivity constraints, the objective is to find a set $E$ of edges such that each $S_i$ induces a connected subgraph of the graph $(V,E)$ and the total cost of $E$ is minimized. First, we study the online version where every constraint must be satisfied immediately after its arrival and edges that have already been added can never be removed. We give an $O(B^{2}logn)$-competitive and $O((B+logr)logn)$-competitive polynomial-time algorithms, where $B$ is an upper bound on the size of constraints, while $r,n$ denote the number of constraints and the number of vertices, respectively. On the other hand, we observe that an $\mathrm{\Omega }(B)$-competitive lower bound as well as an $\mathrm{\Omega }(\sqrt{B})$-competitive lower bound in the cost-uniform case are implied by the known lower bounds for unbounded constraints. For the cost-uniform case with unbounded constraints, we provide an $O(\sqrt{n}(logn+logr))$-competitive upper bound with high probability. The latter bound is against an oblivious adversary while our other randomized competitive bounds are against an adaptive adversary. Next, we discuss a hybrid approximation method for the (offline) Network Construction problem combining an approximation algorithm of Hosoda et al. with one of Angluin et al. and an application of the hybrid method to bioinformatics. Finally, we consider a natural strengthening of the connectivity requirements in the Network Construction problem, where each constraint has to induce a subgraph (of the constructed graph) of diameter at most $d$. Among other things, we provide a polynomial-time $(\left(\genfrac{}{}{0.0pt}{}{B}{2}\right)-B+2)\left(\genfrac{}{}{0.0pt}{}{B}{2}\right)$-approximation algorithm for the Network Construction problem with the $d$-diameter requirements, when each constraint has at most $B$ vertices, and show the APX-completeness of this variant.

A directed projection graph of the $n$-dimensional hypercube on the two-dimensional plane is successfully created. Any $n$-variable Boolean function can be easily transformed to an induced subgraph of the projection. Therefore, the discussions on $n$-variable Boolean functions only need to focus on a two-dimensional planar graph. Some mathematical theories on the projection graph and the induced subgraph are established, and some properties and characteristics of a balanced linearly separable Boolean function (BLSBF) are uncovered. In particular, the sub-hypercube decompositions of BLSBF is easily represented on the projection, and meanwhile, the enumeration scheme for counting the number of $n$-variable BLSBFs is developed by using equivalence classification and conformal transformation. With the aid of the directed projection grap constructed in this paper, one can further study many difficult problems in some fields such as Boolean functions and artificial neural networks.

For a finite graph $\mathrm{\Gamma }$, let $G(\mathrm{\Gamma })$ be the right-angled Artin group defined by the complement graph of $\mathrm{\Gamma }$. We show that, for any linear forest $\mathrm{\Lambda }$ and any finite graph $\mathrm{\Gamma }$, $G(\mathrm{\Lambda })$ can be embedded into $G(\mathrm{\Gamma })$ if and only if $\mathrm{\Lambda }$ can be realized as a full subgraph of $\mathrm{\Gamma }$. We also prove that if we drop the assumption that $\mathrm{\Lambda }$ is a linear forest, then the above assertion does not hold, namely, for any finite graph $\mathrm{\Lambda }$, which is not a linear forest, there exists a finite graph $\mathrm{\Gamma }$ such that $G(\mathrm{\Lambda })$ can be embedded into $G(\mathrm{\Gamma })$, though $\mathrm{\Lambda }$ cannot be embedded into $\mathrm{\Gamma }$ as a full subgraph.

Let claw be the graph K_1,3. A graph G on n ≥ 3 vertices is called o-heavy if each induced claw of G has a pair of end-vertices with degree sum at least n, and called 1-heavy if at least one end-vertex of each induced claw of G has degree at least n/2. In this note, we show that every 2-connected o-heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman and Hedetniemi, Gould and Jacobson, and Shi on the existence of Hamilton cycles in graphs.

In this paper, we present the class of $\delta \mathrm{\text{EFL}}$ graphs and then prove a generalized statement of the Erdős–Faber–Lovász conjecture for this graph class. Then, the Erdős–Faber–Lovász conjecture follows for every graph in this class.

Let $G$ be a graph with $n$ vertices and $m$ edges. The minimum edge dominating energy is equal to the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of graph $G$. In this paper, we establish some bounds for the minimum edge dominating energy of subgraphs of a graph.