Faits : A. A.a. A._ a été nommé en qualité de préposé à l'Office X._ par le Conseil d'Etat du canton du Valais. A la suite de la liquidation d'une succession dont il avait été chargé, le prénommé a fait l'objet d'une procédure pénale ainsi que d'une procédure disciplinaire ouverte par l'autorité de nomination. Le 20 juin 2012, le Conseil d'Etat a décidé de diminuer de moitié le traitement de l'intéressé pour une période de trois mois à compter du 1 er juillet 2012. A._ a été acquitté par la Cour des affaires pénales du Tribunal pénal fédéral par jugement du 29 janvier 2013, confirmé par le Tribunal fédéral par arrêt du 22 juillet 2013 (6B_235/2013). Le recours formé par A._ contre la décision du gouvernement cantonal du 20 juin 2012 a été rejeté par le Tribunal cantonal du Valais (jugement du 24 mai 2013). Saisi d'un recours du prénommé, le Tribunal fédéral a annulé jugement cantonal ainsi que la décision du Conseil d'Etat du 20 juin 2012. Il a condamné le canton du Valais à verser une indemnité de dépens au recourant et a renvoyé la cause à la juridiction précédente pour qu'elle statue à nouveau sur la répartition des frais et dépens de la procédure cantonale (arrêt 8D_3/2013 du 22 juillet 2014, publié aux ATF 140 I 277). A.b. Par jugement du 22 août 2014, le Tribunal cantonal du Valais a notamment alloué à A._ une indemnité de dépens de 2'200 fr. à la charge du canton, précisant dans ses motifs que cette indemnité couvrait ses frais de représentation durant la procédure de recours de droit administratif, l'indemnisation en première instance n'étant dans son principe pas prévue par la loi cantonale sur la procédure et la juridiction administratives (LPJA; RS/VS 172.6). Par décision du 21 janvier 2015, le Conseil d'Etat a constaté que l'arrêt du Tribunal fédéral du 22 juillet 2014 (ATF 140 I 277, ci-dessus mentionné) avait éteint la procédure disciplinaire ouverte à l'encontre de A._ et il a statué sur le traitement auquel celui-ci avait droit depuis le 1 er janvier 2010. B. Par acte du 25 février 2015, le prénommé a recouru devant le Tribunal cantonal en concluant à l'annulation de la décision du 21 janvier 2015 et au renvoi de la cause au Conseil d'Etat. Il a fait valoir notamment que, depuis le 25 août 2014, il avait eu des discussions avec les services d'une conseillère d'Etat et cette dernière en personne, au sujet de son retour dans ses anciennes fonctions de préposé dans un office, discussions au cours desquelles il avait été question non seulement de son traitement, mais aussi des frais d'avocat qu'il avait encourus dans les procédures engagées à son endroit. Préalablement, le 20 février 2015, A._ avait saisi la conseillère d'Etat précitée d'une requête tendant en particulier à ce que le gouvernement cantonal lui accorde une indemnisation pour les frais d'avocat susmentionnés. Au vu de la réponse de la conseillère d'Etat, du 2 mars 2015, selon laquelle sa requête faisait l'objet d'un examen et le Conseil d'Etat statuerait sur les frais d'avocat en cause, l'intéressé a proposé la suspension de la procédure. Consulté par le Tribunal cantonal, le Conseil d'Etat a indiqué, le 13 juillet 2015, qu'il entendait laisser la cour cantonale trancher la question des frais d'avocat. Dans sa détermination du 18 novembre 2015 sur le recours de A._, le gouvernement cantonal a indiqué que sa décision du 21 janvier 2015 comportait la renonciation à attribuer à l'intéressé une indemnité pour ses frais de défense. Par jugement du 18 décembre 2015, la cour cantonale a rejeté le recours. C. A._ interjette un recours en matière de droit public et un recours constitutionnel subsidiaire en concluant à la réforme du jugement attaqué en ce sens que la décision du Conseil d'Etat du 21 janvier 2015 est annulée et l'Etat du Valais condamné à lui payer une indemnité de 19'989 fr. 75 au titre des frais de défense qu'il a supportés et qui n'ont pas été couverts par les dépens alloués en procédure fédérale. Subsidiairement, il demande l'annulation du jugement attaqué et le renvoi de la cause à la cour cantonale pour nouvelle décision. Le Conseil d'Etat conclut à l'irrecevabilité du recours en matière de droit public et, en tout état de cause, au rejet des recours. La cour cantonale a renoncé à se déterminer.