Search

A caterpillar graph $T(p_1, \ldots, p_r)$ of order $n= r+\sum_{i=1}^r p_i$, $r\geq 2$, is a tree such that removing all its pendent vertices gives rise to a path of order $r$. In this paper we establish a necessary and sufficient condition for a real number to be an eigenvalue of the Randi\'c matrix of $T(p_1, \ldots, p_r)$. This result is applied to determine the extremal caterpillars for the Randi\'c energy of $T(p_1,\ldots, p_r)$ for cases $r=2$ (the double star) and $r=3$. We characterize the extremal caterpillars for $r=2$. Moreover, we study the family of caterpillars $T\big(p,n-p-q-3,q\big)$ of order $n$, where $q$ is a function of $p$, and we characterize the extremal caterpillars for three cases: $q=p$, $q=n-p-b-3$ and $q=b$, for $b\in \{1,\ldots,n-6\}$ fixed. Some illustrative examples are included. published

For a (simple) graph $H$ and non-negative integers $c_0,c_1,\ldots,c_d$ ($c_d \neq 0$), $p(H)=\sum_{k=0}^d{c_k \cdot H^k}$ is the lexicographic polynomial in $H$ of degree $d$, where the sum of two graphs is their join and $c_k \cdot H^k$ is the join of $c_k$ copies of $H^k$. The graph $H^k$ is the $k$th power of $H$ with respect to the lexicographic product ($H^0 = K_1$). The spectrum (if $H$ is regular) and the Laplacian spectrum (in general case) of $p(H)$ are determined in terms of the spectrum of $H$ and~$c_k$'s. Constructions of infinite families of cospectral or integral graphs are also announced.

Given a simple and connected graph G with vertex set V , denoting by dG(u) the degree of a vertex u and dG(u, v) the distance of two vertices, the modified Schultz index of G is given by S ∗ P (G) = {u,v}⊆V dG(u) dG(v) dG(u, v), where the summation goes over all non ordered pairs of vertices of G. In this paper we consider some graph operations, namely cartesian product, complete product, composition and subdivision, and we obtain explicit formulae for the modified Schultz index of a graph in terms of the number of vertices and edges as well as some other topological invariants such as the Wiener index, the Schultz index and the first and second Zagreb indices.

Let G be a simple graph on $n$ vertices and $e(G)$ edges. Consider $Q(G) = D + A$ as the signless Laplacian of $G$, where $A$ is the adjacency matrix and $D$ is the diagonal matrix of the vertices degree of $G$. Let $q_1(G)$ and $q_2(G)$ be the first and the second largest eigenvalues of $Q(G),$ respectively, and denote by $S_{n}^{+}$ the star graph plus one edge. In this paper, we prove that inequality $q_1(G)+ q_2(G)

A subset of the vertex set of a graph G , W ⊆ V ( G ) , is a ( k , τ ) -regular set if it induces a k -regular subgraph of G and every vertex not in the subset has τ neighbors in it. In this paper we deal with the existence of ( k , τ ) -regular sets associated with all distinct eigenvalues. We show some families that have this property and we give some results concerning the existence of such sets considering restrictions on the symbol of circulant graphs.

A set of vertices S@?V(G) is (k,@t)-regular if it induces a k-regular subgraph of G such that |N"G(v)@?S|=@t@?v@?S. Note that a connected graph with more than one edge has a perfect matching if and only if its line graph has a (0,2)-regular set. In this paper, some spectral results on the adjacency matrix of graphs with (k,@t)-regular sets are presented. Relations between the combinatorial structure of a p-regular graph with a (k,@t)-regular set and the eigenspace corresponding to each eigenvalue @l@?{p,k-@t} are deduced. Finally, additional results on the effects of Seidel switching (with respect to a bipartition induced by S) of regular graphs are also introduced.

In spectral graph theory a graph with least eigenvalue −2 is exceptional if it is connected, has least eigenvalue greater than or equal to −2, and it is not a generalized line graph. A (κ,τ)-regular set S of a graph is a vertex subset, inducing a κ-regular subgraph such that every vertex not in S has τ neighbors in S. We present a recursive construction of all regular exceptional graphs as successive extensions by regular sets. The authors I. Barbedo, D. M. Cardoso and P. Rama were partially supported by Portuguese funds through the CIDMA - Center for Research and Development in Mathematics and Applications, and the Portuguese Foundation for Science and Technology (“FCT-Funda¸c˜ao para a Ciˆencia e a Tecnologia”), within project PEst-OE/MAT/UI4106/2014. info:eu-repo/semantics/publishedVersion

A food bank is a non-profit, social solidarity organisation that typically distributes the donated food among a wide variety of local non-profit, social solidarity institutions which in turn feed the low-income people. The problem presented by the Portuguese Federation of Food Banks is to determine, for a specific food bank, the quantities of the donated products that must be assigned to each local social solidarity institution in order to satisfy the needs of the supported people as much as possible, without favouring any institution. We propose a linear programming model followed by a rounding heuristic to obtain a solution to the problem described. Computational results are reported.

Graphs with (k, τ)-regular sets and equitable partitions are examples of graphs with regularity constraints. A (k, τ)-regular set of a graph G is a subset of vertices S ⊆ V(G) inducing a k-regular subgraph and such that each vertex not in S has τ neighbors in S. The existence of such structures in a graph provides some information about the eigenvalues and eigenvectors of its adjacency matrix. For example, if a graph G has a (k1, τ1)-regular set S1 and a (k2, τ2)-regular set S2 such that k1 − τ1 = k2 − τ2 = λ, then λ is an eigenvalue of G with a certain eigenvector. Additionally, considering primitive strongly regular graphs, a necessary and sufficient condition for a particular subset of vertices to be (k, τ)-regular is introduced. Another example comes from the existence of an equitable partition in a graph. If a graph G, has an equitable partition π then its line graph, L(G), also has an equitable partition, π ¯ , induced by π, and the adjacency matrix of the quotient graph L ( G ) / π ¯ is obtained from the adjacency matrix of G/π.

Submitted by Domingos Cardoso (dcardoso@ua.pt) on 2011-10-18T16:51:50Z No. of bitstreams: 1 CardosoDElormeRama.pdf: 205743 bytes, checksum: eac5abcf59a3e7c081028afa5af8f1fa (MD5) Made available in DSpace on 2011-11-10T10:52:32Z (GMT). No. of bitstreams: 1 CardosoDElormeRama.pdf: 205743 bytes, checksum: eac5abcf59a3e7c081028afa5af8f1fa (MD5) Previous issue date: 2007 CEOC FCT FEDER