I'm not sure what is the final goal and/or application of this process. But let me try to do this task (since this "puzzle" will be a good excerise for me!)
% Create Graph object with fixed node name
s = [1 2 2 4 5 4 8 7 7 8 13];
t = [3 3 11 5 6 6 7 10 12 12 9];
G = graph(s,t,[],compose('%d',1:13));
% Separate G to subgraphs
group = conncomp(G,'OutputForm','cell');
subGraph = cellfun(@(x) subgraph(G,x),group,'UniformOutput',false);
% Initialize the output cell array (= result)
C_out = cell(1,numel(subGraph));
for kk1 = 1:numel(subGraph)
% kk1-th subgraph
G = subGraph{kk1};
nodes = G.Nodes.Name';
c = cell(1,numel(nodes));
% Find non-neighbouring nodes for each node and create the output cell
% arrray for each subgraph
for kk2 = 1:numel(nodes)
nextNodes = neighbors(G,nodes{kk2})';
nonNextNodes = setdiff(nodes,[nodes(kk2),nextNodes]);
if isempty(nonNextNodes)
c{kk2} = str2double(nodes(kk2));
else
[~,pt] = sort(str2double(nonNextNodes));
c{kk2} = str2double(nonNextNodes(pt));
end
end
% Store the result for each subgraph
C_out{kk1} = c;
end
