Modelling a problem in Graph Theory language

I am trying to model the following problem that I found in the AI field in graph theory language, but I have limited experience in graphs.

We consider a network of devices. If two devices are close enough they can communicate directly, otherwise they have to communicate through intermediate devices. In case they do not communicate with any other device they work with limited energy in order to preserve their battery. For that reason we want to find a subset of devices which can work in alert state and act as intermediate devices. These intermediate devices must be chosen as follows :

• Each network device should be able to communicate directly with at least one intemediate device
• All network messages should pass through intermediate devices. An intemediate device should be able to pass a message to another intermediate device either directly or through a third one.

My attempt was to see if a statement similar to the below holds, because it resembles the above problem:

For every connected graph (V,E) there exists a connected subgraph (V',E') such that " for all $u\in V\V'$ there exists at least one $e\in E$ which connects u with a V' vertex" .

Does the graph theory statement describe the above problem? Are you aware of any well-known problems in logic and/or discrete maths modelled like my problem ?

Any remark is welcome.

The statement you want describes the situation with intermediate devices, but it doesn't fully describe the problem, because it doesn't fully say what you want: to find the smallest number of intermediate devices you can have.

So we might say that your goal is to find the smallest connected subgraph $G' = (V', E')$ such that every $u \in V \setminus V'$ is adjacent to some $v \in V'$.

There are two ways to describe this problem that are more standard, though not really any more helpful. But you'll know the terminology people use, at least.

1. The set $V'$ is a connected dominating set of $G$. Here, "dominating set" refers to the requirement that every $u \in V \setminus V'$ is adjacent to some $v \in V'$. You additionally want the subgraph induced by $V'$ to be connected.

2. Consider just the minimum set of edges that does what you want: enough edges to connect $G'$, and a single edge from every $u \in V \setminus V'$ to some $v \in V'$. This is a spanning tree of $G$, and every vertex outside $V'$ is a leaf: a vertex with only one edge out of it. Also, every leaf of the spanning tree might as well not be part of $V'$, because it isn't part of any paths connecting other vertices.

So we can say that your goal is either

• to find the smallest connected dominating set of $G$, or
• to find a spanning tree of $G$ with the most leaves.